Codeforces 455D 分块+链表

题意：

给定一个长度为 N 的序列
两种操作
1 l r 将[l,r]的数向右循环移位
2 l r 询问[l,r]内有多少个数等于 k
其中 N,Q≤10⁵,ai≤N
强制在线

思路：

每块用一个链表维护一下
位移的话由于是链表，操作速度很快
然后每个数都不超过 N，所以用一个数组记录一下每块每个数的个数
总的复杂度就是 O(Qsqrt(N))

如果不考虑那个奇怪的询问的话，可以简单地用splay树维护序列。但是splay上显然不能维护每种颜色的个数，这样在每个节点上时间和空间都是O(n)的。
我们把给每种颜色的节点单独建一棵splay，每个节点放在两棵splay中，一棵是原序列，一棵是它自己的颜色。接下来考虑如何进行插入、询问和删除操作。
删除操作比较简单，只需要在大splay上找到对应的节点，在两棵树中先旋转到底再自下而上删除。
插入和询问都可以在小splay上走，通过在大splay上的询问就可以知道当前节点在序列中的位置。
复杂度O((n+q)log2n)。

from yhx

//By SiriusRen

#include <bits/stdc++.h>

using namespace std;

const int N=;

int n,q,a[N],wei[][N],l[],r[],block[N],lastans;

list<int>lst[];

list<int>::iterator it,it2;

void make_list(){

    for(int i=;i<=block[n];i++)

        for(int j=l[i];j<=r[i];j++)

            lst[i].push_back(a[j]),wei[i][a[j]]++;

}

void work(int x,int y){

    int t=y-l[block[y]],tmp,rem;

    for(it=lst[block[y]].begin();t;t--,it++);

    rem=*it;wei[block[y]][rem]--;

    lst[block[y]].erase(it);

    for(int i=block[x];i<block[y];i++){

        it=lst[i].end(),it--,tmp=*it,lst[i].erase(it);

        lst[i+].push_front(tmp);

        wei[i][tmp]--,wei[i+][tmp]++;

    }

    t=x-l[block[x]];

    for(it=lst[block[x]].begin();t;t--,it++);

    lst[block[x]].insert(it,rem);wei[block[x]][rem]++;

}

int query(int x,int y,int z){

    int ans=,t=x-l[block[x]],ty;

    if(block[x]==block[y]){

        for(it=lst[block[x]].begin();t;t--,it++);

        ty=y-l[block[y]]+;

        for(it2=lst[block[x]].begin();ty;ty--,it2++);

        for(;it!=it2;it++){if(*it==z)ans++;}

        return ans;

    }

    for(int i=block[x]+;i<block[y];i++)ans+=wei[i][z];

    for(it=lst[block[x]].begin();t;t--,it++);

    for(;it!=lst[block[x]].end();it++)if(*it==z)ans++;

    t=y-l[block[y]]+;

    for(it=lst[block[y]].begin();t;it++,t--)if(*it==z)ans++;

    return ans;

}

int main(){

    memset(l,0x3f,sizeof(l)),scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    int Block=1.6*sqrt(n);

    for(int i=;i<=n;i++)block[i]=(i-)/Block+,l[block[i]]=min(l[block[i]],i),r[block[i]]=i;

    make_list();

    scanf("%d",&q);

    while(q--){

        int op,xx,yy,zz;

        scanf("%d%d%d",&op,&xx,&yy);

        xx=(xx+lastans-)%n+,yy=(yy+lastans-)%n+;

        if(xx>yy)swap(xx,yy);

        if(op==)work(xx,yy);

        else scanf("%d",&zz),printf("%d\n",lastans=query(xx,yy,(zz+lastans-)%n+));

    }

}

巴特西

Codeforces 455D 分块+链表

最新文章

热门文章