社区讨论
本人父亲在晚上梦游时候删掉我的代码,导致我重构结果直接RE,求助
CF785E Anton and Permutation参与者 8已保存回复 12
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 12 条
- 当前快照
- 1 份
- 快照标识符
- @lzig9wop
- 此快照首次捕获于
- 2024/08/06 21:22 2 年前
- 此快照最后确认于
- 2024/08/06 22:44 2 年前
RE on #5
CPP#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=2e5+5,NN=505;
int n,q,a[N],l[NN],r[NN],id[NN],len,ans;
vector<int>b[NN];
void upd(int id1,int id2)
{
if(id[id1]!=id[id2])
{
b[id[id1]].erase(lower_bound(b[id[id1]].begin(),b[id[id1]].end(),a[id1]));
b[id[id1]].insert(upper_bound(b[id[id1]].begin(),b[id[id1]].end(),a[id2]),a[id2]);
b[id[id2]].erase(lower_bound(b[id[id2]].begin(),b[id[id2]].end(),a[id2]));
b[id[id2]].insert(upper_bound(b[id[id2]].begin(),b[id[id2]].end(),a[id1]),a[id1]);
}
swap(a[id1],a[id2]);
}
int query(int x,int y,int val)
{
int res=0;
if(id[x]==id[y])
{
for(int i=x;i<=y;i++)
if(a[i]<val)
res++;
return res;
}
for(int i=x;i<=r[id[x]];i++)
if(a[i]<val)
res++;
for(int i=id[x]+1;i<id[y];i++)
res+=lower_bound(b[i].begin(),b[i].end(),val)-b[i].begin();
for(int i=l[id[y]];i<=y;i++)
if(a[i]<val)
res++;
return res;
}
signed main()
{
scanf("%lld%lld",&n,&q);
for(int i=1;i<=n;i++)
a[i]=i;
len=sqrt(n);
for(int i=1;i<=len;i++)
l[i]=(i-1)*len+1,r[i]=i*len;
if(r[len]!=n)
l[len+1]=r[len]+1,r[len+1]=n,len++;
for(int i=1;i<=len;i++)
for(int j=l[i];j<=r[i];j++)
b[i].pb(a[j]);
while(q--)
{
int id1,id2;
scanf("%lld%lld",&id1,&id2);
if(id1>id2)
swap(id1,id2);
if(id1==id2)
{
printf("%lld\n",ans);
continue;
}
ans+=2*(query(id1+1,id2-1,a[id2])-query(id1+1,id2-1,a[id1]));
ans+=(a[id2]>a[id1])?1:-1;
upd(id1,id2);
printf("%lld\n",ans);
}
return 0;
}
回复
共 12 条回复,欢迎继续交流。
正在加载回复...