题目概述

HDU7185

解题报告

其实并不难。由于每次区间操作都是直接覆盖成一种颜色，所以我们可以考虑用set维护所有的颜色相同的线段，然后每次操作就是对set中的线段进行分裂以及合并，复杂度分析和线段树的分裂与合并是一样的，总共需要分裂或者合并 $O(q)$ 次（在随机数据下，这种做法被称为珂朵莉树，因为随机数据下块数不超过 $\log\log n$ ，虽然和这题没什么关系）。

然后对于颜色整体加和单点查询，就利用经典的技巧：维护整体加的tag，然后每次区间 $[L,R]$ 颜色转换时，把更改颜色的贡献区间加到 $[L,R]$ 上，例如 $pos$ 位置从 $c$ 颜色变成了 $d$ 颜色，列出等式 $tag_c+ask(pos)=tag_d+ask'(pos)$ ，得到 $ask'(pos)-ask(pos)=tag_c-tag_d$ ，因此进行 $[L,R]$ 上整体加 $tag_c-tag_d$ 即可。

示例程序

这个 $1$ 操作说的最近 $2c$ 个点是真的最近 $2c$ 个点……如果顶到头就需要往另一边扩展（玩文字游戏是吧）。

#include<set>
#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxq=100000,maxt=2e7;

int te,n,Q;LL tag[maxq+5];
struct node{
    int L,R,c;
    node(int l=0,int r=0,int w=0) {L=l;R=r;c=w;}
    bool operator < (const node &a) const {return L<a.L;}
};
typedef set<node>::iterator SI;
set<node> S;SI it,l,r;
int pl,ro,ls[maxt+5],rs[maxt+5];LL sum[maxt+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
struct fastO{
    int si;char buf[100000];
    fastO() {si=0;}
    void putc(char ch){
        if (si==100000) fwrite(buf,1,si,stdout),si=0;
        buf[si++]=ch;
    }
    ~fastO() {fwrite(buf,1,si,stdout);}
}fo;
template<typename T> void writei(T x,char ch='\n'){
    int len=0,buf[100];
    if (x<0) fo.putc('-'),x=-x;
    do buf[len++]=x%10,x/=10; while (x);
    while (len) fo.putc(buf[--len]+48);
    fo.putc(ch);
}
inline int newnode() {pl++;ls[pl]=rs[pl]=sum[pl]=0;return pl;}
void Insert(int &p,int L,int R,LL k,int l=1,int r=n){
    if (!p) p=newnode();
    if (L==l && r==R) {sum[p]+=k;return;}
    int mid=l+(r-l>>1);
    if (R<=mid) Insert(ls[p],L,R,k,l,mid); else if (L>mid) Insert(rs[p],L,R,k,mid+1,r);
    else Insert(ls[p],L,mid,k,l,mid),Insert(rs[p],mid+1,R,k,mid+1,r);
}
LL Ask(int p,int pos,LL now=0,int l=1,int r=n){
    if (!p) return now;now+=sum[p];
    if (l==r) return now;
    int mid=l+(r-l>>1);
    return pos<=mid?Ask(ls[p],pos,now,l,mid):Ask(rs[p],pos,now,mid+1,r);
}
inline SI Node(int x) {return prev(S.upper_bound(node(x,1e9)));}
SI Split(int x){
    if (x>n) return S.end();
    it=Node(x);if (it->L==x) return it;
    int L=it->L,R=it->R,c=it->c;
    S.erase(it);S.insert(node(L,x-1,c));
    return S.insert(node(x,R,c)).first;
}
void Assign(int L,int R,int c){
    r=Split(R+1);l=Split(L);
    for (it=l;it!=S.end() && it->R<=R;it=S.erase(it))
        Insert(ro,it->L,it->R,tag[it->c]-tag[c]);
    S.insert(node(L,R,c));
}
void Cover(int x,int y,int c){
    int L=max(x-y,1),R=L+y+y;
    if (R>n) R=n,L=R-y-y;
    Assign(L,R,c);
}
void Copy(int x,int y){
    l=r=Node(y);int Y=l->c;
    while (l!=S.begin() && prev(l)->c==Y) l=prev(l);
    while (next(r)!=S.end() && next(r)->c==Y) r=next(r);
    Assign(l->L,r->R,Node(x)->c);
}
int main(){
    for (readi(te);te;te--){
        readi(n);readi(Q);
        for (int i=0;i<=Q;i++) tag[i]=0;
        S.clear();S.insert(node(1,n,0));
        pl=ro=0;
        LL lstans=0;
        for (int t=1,tp,x,y;t<=Q;t++){
            readi(tp);readi(x);x=((x-1)^lstans)%n+1;
            if (tp==1) readi(y),y=((y-1)^lstans)%((n-1)/2)+1,Cover(x,y,t); else
            if (tp==2) readi(y),y=((y-1)^lstans)%n+1,Copy(x,y); else
            if (tp==3) readi(y),tag[Node(x)->c]+=y;
            else lstans=Ask(ro,x)+tag[Node(x)->c],writei(lstans),lstans&=1073741823;
        }
    }
    return 0;
}