[DS记录]P5066 [Ynoi2014] 人人本着正义之名
command_block
2021-06-29 11:36:22
**题意** : 维护一个长为 $n$ 的 `01`序列 $A$ ，有如下 $m$ 个操作：
- 把区间 $[l,r]$ 的数变成 $0$。
- 把区间 $[l,r]$ 的数变成 $1$。
- $[l,r-1]$ 内所有数 $a_i$，变为 $a_i$ 与 $a_{i+1}$ 按位或的值，这些数同时进行这个操作。
- $[l+1,r]$ 内所有数 $a_i$，变为 $a_i$ 与 $a_{i-1}$ 按位或的值，这些数同时进行这个操作。
- $[l,r-1]$ 内所有数 $a_i$，变为 $a_i$ 与 $a_{i+1}$ 按位与的值，这些数同时进行这个操作。
- $[l+1,r]$ 内所有数 $a_i$，变为 $a_i$ 与 $a_{i-1}$ 按位与的值，这些数同时进行这个操作。
- 查询区间 $[l,r]$ 的和。
强制在线，$n,m\leq 3\times 10^6$ ，时限$\texttt{8s}$ ，空限$\texttt{512M}$。
------------
不难发现，操作相当于“区间内的 $0/1$ 连续段向 左/右 扩展一位”.
用平衡树维护极长 $01$ 连续段的左端点，以及颜色。
当某个颜色扩展时，若存在长度为 $1$ 的另一种颜色的连续段，则需要将其删除，并将两侧的连续段合并。（需要特殊考虑边界情况）
若某棵子树中不存在删除事件，则可以打标记维护。标记有两种 :“颜色 $0/1$ 前扩， $1/0$ 后缩”。
维护 $1$ 段的个数，两类段的最短长度（若不存在则为 $+\infty$，用于判定是否有删除事件），以及和。
连续段的个数是 $O(n+m)$ 的，于是花费在删除事件上的额外复杂度可以保证。
实现中用 leafy-Tree 维护。复杂度 $O\big((n+m)\log n\big)$。
本质不难，细节真多。
一不小心拿了个最优解。
leafy-Tree 牛逼！
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
#define MaxN 3000500
using namespace std;
namespace io {
char buf[5005000],*p1=buf,*p2=buf,obuf[5005000],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,5000000,stdin),p1==p2)?EOF:*p1++)
int rd() {
int x=0;char ch=getchar();
while(ch<'0'||'9'<ch)ch=getchar();
while('0'<=ch&&ch<='9')x=x*10+(ch^48),ch=getchar();
return x;
}
void putc(char ch){*O++=ch;}
void print(ll x){if(x>9)print(x/10);*O++=x%10+'0';}
void flush(bool op=0){if (O-obuf>=5000000||op){fwrite(obuf,O-obuf,1,stdout);O=obuf;}}
}using namespace io;
const int INF=1000000000;
struct Node{
int l,r,s,c,tg[2],x[2],p;bool v;
// t[v] ′ú±í??é? v ?°à?￡? !v ?òoó??
inline void ladd(int t0,int t1){
tg[0]+=t0;tg[1]+=t1;p-=(v==0) ? t0 : t1;
x[0]+=t0-t1;x[1]+=t1-t0;s+=c*(t1-t0);
}
}a[MaxN<<1];
int tot,rub[MaxN],top;
int cre(){
if (top){
int u=rub[top--];
memset(&a[u],0,sizeof(Node));
return u;
}return ++tot;
}
inline void Init(int l,int r,int v,Node &A)
{A.p=l;A.v=v;A.x[v]=r-l+1;A.x[!v]=INF;A.c=v;A.s=v*(r-l+1);}
inline void up(int u){
int l=a[u].l,r=a[u].r;
a[u].p=a[l].p;a[u].v=a[l].v;
a[u].c=a[l].c+a[r].c;
a[u].s=a[l].s+a[r].s;
a[u].x[0]=min(a[l].x[0],a[r].x[0]);
a[u].x[1]=min(a[l].x[1],a[r].x[1]);
}
inline void ladd(int u){
if (a[u].tg[0]||a[u].tg[1]){
a[a[u].l].ladd(a[u].tg[0],a[u].tg[1]);
a[a[u].r].ladd(a[u].tg[0],a[u].tg[1]);
a[u].tg[0]=a[u].tg[1]=0;
}
}
inline int merge(int l,int r){
int u=cre();a[u].l=l;a[u].r=r;
up(u);return u;
}
int sl[MaxN],sm[MaxN],sr[MaxN],tl,tm,tr;
int n,rt,wfl,wfr;
void spiltl(int u){
if (!a[u].l){sm[++tm]=u;return ;}
ladd(rub[++top]=u);
spiltl(a[u].l);sm[++tm]=a[u].r;
}
void spiltr(int u){
if (!a[u].r){sm[++tm]=u;return ;}
ladd(rub[++top]=u);
sm[++tm]=a[u].l;spiltr(a[u].r);
}
int flag;
void spilt(int l=1,int r=n,int u=rt)
{
if (r<wfl-1||(!a[u].l&&r<wfl)){sl[++tl]=u;return ;}
if (wfr+1<l||(!a[u].l&&wfr<l)){sr[++tr]=u;return ;}
if ((wfl<l&&r<wfr&&(flag==2||a[u].x[!flag]>1))||!a[u].l)
{sm[++tm]=u;return ;}
ladd(rub[++top]=u);int mid=a[a[u].r].p-1;
spilt(l,mid,a[u].l);spilt(mid+1,r,a[u].r);
}
int s[MaxN<<1];
void build()
{
int tn=0;
memcpy(s+1,sl+1,sizeof(int)*tl);tn=tl;
memcpy(s+tn+1,sm+1,sizeof(int)*tm);tn+=tm;
memcpy(s+tn+1,sr+1,sizeof(int)*tr);tn+=tr;
while(tn>1){
for (int i=2;i<=tn;i+=2)
s[i/2]=merge(s[i-1],s[i]);
if (tn&1)s[(tn+1)/2]=s[tn];
tn=(tn+1)/2;
}rt=s[1];tl=tm=tr=0;
}
int m,x[MaxN];
int main()
{
n=rd();m=rd();
for (int i=1;i<=n;i++)x[i]=rd();
x[n+1]=-1;
for (int i=1,p=1;i<=n;i++)
if (x[i]!=x[i+1]){
Init(p,i,x[i],a[sm[++tm]=cre()]);
p=i+1;
}
build();
#define fir sm[1]
#define las sm[tm]
for (int i=1,op,tn,last=0;i<=m;i++){
op=rd();wfl=rd()^last;wfr=rd()^last;
if (3<=op&&op<=6&&wfl==wfr)continue;
if (op==3||op==4)flag=1;
if (op==5||op==6)flag=0;
if (op<3||op>6)flag=2;
spilt();
if (op==1||op==2){
op--;
int vl=a[fir].v,l=a[fir].p
,vr=a[las].v,r=a[las].p+a[las].x[vr]-1;
for (int i=1;i<=tm;i++)rub[++top]=sm[i];tm=0;
if (vl!=op&&l<wfl)Init(l,wfl-1,vl,a[sm[++tm]=cre()]);
Init((vl==op) ? l : wfl,(vr==op) ? r : wfr,op,a[sm[++tm]=cre()]);
if (vr!=op&&wfr<r)Init(wfr+1,r,vr,a[sm[++tm]=cre()]);
}
if (3<=op&&op<=6){
memcpy(s+1,sm+1,sizeof(int)*tm);
tn=tm;tm=0;
for (int i=1;i<=tn;i++){
if (tm&&a[s[i]].x[!flag]==1)
spiltr(sm[tm--]);
if (tm&&a[sm[tm]].x[!flag]==1)
spiltl(s[i]);
else sm[++tm]=s[i];
}memcpy(s+1,sm+1,sizeof(int)*tm);
tn=tm;tm=0;
}
if (op==3||op==5){
bool fl=(a[s[tn]].v!=flag);if (fl)tn--;
if (tn&&a[s[1]].x[!flag]>1){
int u=sm[tm=1]=s[1];
if (a[u].v!=flag)a[u].ladd(flag==0,flag==1);
}
for (int i=2;i<=tn;i++)
if (a[s[i]].x[!flag]==1){
i++;
int l=a[sm[tm]].p,r=a[s[i]].p+a[s[i]].x[flag]-1;
rub[++top]=sm[tm--];rub[++top]=s[i];
Init(l,r,flag,a[sm[++tm]=cre()]);
}else a[sm[++tm]=s[i]].ladd(flag==0,flag==1);
if (fl)sm[++tm]=s[tn+1];
}
if (op==4||op==6){
reverse(s+1,s+tn+1);
bool fl=(a[s[tn]].v!=flag);if (fl)tn--;
if (tn&&a[s[1]].x[!flag]>1){
int u=sm[tm=1]=s[1];
if (a[u].v!=flag)a[u].ladd(-(flag==1),-(flag==0));
}
for (int i=2;i<=tn;i++)
if (a[s[i]].x[!flag]==1){
i++;
int l=a[s[i]].p,r=a[sm[tm]].p+a[sm[tm]].x[flag]-1;
rub[++top]=s[i];rub[++top]=sm[tm--];
Init(l,r,flag,a[sm[++tm]=cre()]);
}else a[sm[++tm]=s[i]].ladd(-(flag==1),-(flag==0));
if (fl)sm[++tm]=s[tn+1];
reverse(sm+1,sm+tm+1);
}
if (op==7){
int ans=0;
if (tm==1)ans=a[fir].v*(wfr-wfl+1);
else {
for (int i=2;i<tm;i++)ans+=a[sm[i]].s;
if (a[fir].v)ans+=a[fir].s-wfl+a[fir].p;
if (a[las].v)ans+=wfr-a[las].p+1;
}print(last=ans);putc('\n');flush();
}else {
if (tl&&a[sm[1]].p==wfl&&a[sl[tl]].v==a[sm[1]].v){
int v=a[sm[1]].v,l=a[sl[tl]].p,r=a[sm[1]].p+a[sm[1]].x[v]-1;
rub[++top]=sl[tl--];rub[++top]=sm[1];
Init(l,r,v,a[sm[1]=cre()]);
}
if (tr&&a[sr[1]].p==wfr+1&&a[sm[tm]].v==a[sr[1]].v){
int v=a[sr[1]].v,l=a[sm[tm]].p,r=a[sr[1]].p+a[sr[1]].x[v]-1;
rub[++top]=sm[tm--];rub[++top]=sr[1];
Init(l,r,v,a[sr[1]=cre()]);
}
}build();
}flush(1);
return 0;
}
```