社区讨论

本人父亲在晚上梦游时候删掉我的代码,导致我重构结果直接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 条回复,欢迎继续交流。

正在加载回复...