题解：P4807 [CCC2017] 地铁交通

· · 题解

模拟赛题，不用根号分治纯分块做法。

思路：

首先有一种显然的根号分治算法，不优化是 n\sqrt {n\log n} 结合数据范围想到写根号算法。考虑分块，首先按所属的环分类，发现对于修改操作的维护是简单的，对于一个块内发现最后一个数会移到下一个块内，其它数对于一个块的和是无影响的，可以不考虑。于是就有一个思路，每一个块内开一个队列，维护队头就行。发现空间复杂度带根号，如果出题人要卡空间就做不了，发现分类后每一块的最后一个数是可以直接求出的，每次踢队就相当于把最后一个数变成上一个数。再考虑查询操作，考虑散块部分怎么做，对于一种颜色算出需要几个，从块内最后一个向前找就行。经过精细实现空间线性，时间 O(n\sqrt n)。

Code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace IO
{
    char buff[1<<21],*p1=buff,*p2=buff;
    char getch(){return p1==p2&&(p2=((p1=buff)+fread(buff,1,1<<21,stdin)),p1==p2)?EOF:*p1++;}
    template<typename T>void read(T &x){char ch=getch();int fl=1;x=0;while(ch>'9'||ch<'0'){if(ch=='-')fl=-1;ch=getch();}while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getch();}x*=fl;}
    template<typename T>void read_s(T &x){char ch=getch();while(ch<'a'||ch>'z')ch=getch();while(ch>='a'&&ch<='z'){x+=ch;ch=getch();}}
    template<typename T,typename ...Args>void read(T &x,Args& ...args){read(x);read(args...);}
    char obuf[1<<21],*p3=obuf;
    void putch(char ch) {if(p3-obuf<(1<<21))*p3++=ch;else fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=ch;}
    char ch[100];
    template<typename T>void write(T x) {if(!x)return putch('0');if(x<0)putch('-'),x*=-1;int top=0;while(x)ch[++top]=x%10+48,x/=10;while(top)putch(ch[top]),top--;}
    template<typename T,typename ...Args>void write(T x,Args ...args) {write(x);write(args...);}
    void put(string s){for(int i=0;i<s.size();i++)putch(s[i]);}
    void flush(){fwrite(obuf,p3-obuf,1,stdout);}
}
using namespace IO;
int n,m,q;
int c[150005];
ll a[150005];
int siz,bcnt,belong[150005],bl[400],br[400];
ll sum[400];
int vis[150005];
struct node
{
    int id,p;
};
vector<node>v[150005],tag[150005];
vector<int>p[150005];
int tc[150005],tc1[150005];
inline ll calc(int x,int y)
{
    ll res=0;int b=belong[x];
    for(int i=x;i<=y;i++) ++tc[c[i]];
    for(int i=y+1;i<=br[b];i++) ++tc1[c[i]];
    for(int i=0;i<v[b].size();i++) 
    {
        int nc=v[b][i].id;
        int now=tag[nc][v[b][i].p].p;
        while(tc1[nc])
        {
            --now;if(now==-1) now=p[nc].size()-1;
            --tc1[nc];
        }
        while(tc[nc])
        {
            res+=a[p[nc][now]];
            --now;if(now==-1) now=p[nc].size()-1;
            --tc[nc];
        }
    }
    return res;
}
signed main()
{
    freopen("ring.in","r",stdin);
    freopen("ring.out","w",stdout);
    read(n,m,q);
    siz=sqrt(n);
    bcnt=ceil(1.0*n/siz);
    for(int i=1;i<=bcnt;i++)
    {
        bl[i]=(i-1)*siz+1,br[i]=min(n,i*siz);
        for(int j=bl[i];j<=br[i];j++) belong[j]=i;
    }
    for(int i=1;i<=n;i++) read(c[i]),p[c[i]].push_back(i);
    for(int i=1;i<=n;i++) read(a[i]),sum[belong[i]]+=a[i];
    for(int i=1;i<=m;i++) p[i].push_back(n+1);
    for(int i=1;i<=bcnt;i++)
    {
        for(int j=bl[i];j<=br[i];j++)
            if(!vis[c[j]]) v[i].push_back((node){c[j],0}),vis[c[j]]=1;
        for(int j=0;j<v[i].size();j++) 
        {
            int x=v[i][j].id;
            int pos=upper_bound(p[x].begin(),p[x].end(),br[i])-p[x].begin()-1;
            tag[x].push_back((node){i,pos}),vis[x]=0;
            v[i][j].p=tag[x].size()-1;
        }
    }
    for(int i=1;i<=m;i++) p[i].pop_back();
    while(q--)
    {
        int op,x,y;
        read(op,x);
        if(op==1)
        {
            read(y);
            ll ans=0;
            if(belong[x]==belong[y])
            {
                write(calc(x,y)),putch('\n');
                continue;
            }
            for(int i=belong[x]+1;i<=belong[y]-1;i++) ans+=sum[i];
            ans+=calc(x,br[belong[x]])+calc(bl[belong[y]],y);
            write(ans),putch('\n');
        }
        else
        {
            if(tag[x].size()==0) continue;
            node tmp=tag[x].back();
            for(int i=tag[x].size()-1;i;i--)
            {
                sum[tag[x][i].id]+=a[p[x][tag[x][i-1].p]]-a[p[x][tag[x][i].p]];
                --tag[x][i].p;if(tag[x][i].p==-1) tag[x][i].p=p[x].size()-1;
            }
            sum[tag[x][0].id]+=a[p[x][tmp.p]]-a[p[x][tag[x][0].p]];
            --tag[x][0].p;if(tag[x][0].p==-1) tag[x][0].p=p[x].size()-1;
        }
    }
    flush();
    return 0;
}