[DS记录]P5113 Sabbat of the witch
command_block
2021-06-26 10:26:30
**题意** ： 维护长为 $n$ 的序列 $A$，支持以下三种操作
- 区间赋值
- 区间求和
- 撤回之前的某个区间赋值操作
强制在线， $n,q\leq 10^5$ ，保证区间赋值不超过 $6.5\times 10^4$ 次，时限$\texttt{1.5s}$ ，空限$\texttt{500Mb}$。
------------
考虑序列分块。
对于每个元素，用栈维护散块修改。对于每个块，也用栈维护整块修改。链表以时间为序，末端即为最晚的修改。
（为了节省空间，用链表维护栈）
删除时打标记并懒惰删除。
这样，我们容易 $O(1)$ 查某个位置的值。询问时，只需取出整块的和，对于散块直接暴力。
接下来的任务是维护整块的和。
记块大小为 $B$ ，整块的最后修改为 $(x,tim)$ ，且 $tim$ 之后的散块修改个数为 $c'$ 权值为 $w$ ，则最终该块的权值和为 $x*(B-c')+w$。
撤回某个修改时，对于某个块，最后修改时间可能变化，我们要快速求出该块的和。
于是我们对每个元素的 $(x,tim)$ 二元组排序，然后二分找出一个后缀。
区间赋值时，整块修改后的和易得。
对于修改中的散块，需要重构。对各个元素的 $(x,tim)$ 二元组进行基数排序。
时空复杂度均为 $O(n\sqrt{n\log n})$。轻微卡常。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
#define MaxN 100500
#define MaxC 65500
using namespace std;
int col[MaxC],sl[MaxC],sr[MaxC],tq;
bool vis[MaxC];
struct Line{int t,nxt;}l[MaxC*600];
int fir[MaxN],tl;
void adl(int u,int x)
{l[++tl]=(Line){x,fir[u]};fir[u]=tl;}
int BS,st[260][MaxC],top[260];
void pop(int k)
{
int bl=k*BS,br=bl+BS;
for (int i=bl;i<br;i++)
while(vis[l[fir[i]].t])
fir[i]=l[fir[i]].nxt;
}
int t[MaxN];ll w[MaxN],sb[260];
int s1[405],s2[405],o[260];
void upd(int k){
int bl=k*BS,br=bl+BS,bt=st[k][top[k]]
,i=lower_bound(t+bl,t+br,bt)-t;
sb[k]=1ll*(i-bl)*col[bt]+(i<br ? w[i] : 0);
}
int a[MaxN];
void build(int k)
{
int bl=k*BS,br=bl+BS,tn=0,tn2=bl-1;
for (int i=bl;i<br;i++){
int now=l[fir[i]].t;
if (now)o[(s1[++tn]=now)&255]++;
else {t[++tn2]=0;w[tn2]=a[i];}
}for (int i=1;i<256;i++)o[i]+=o[i-1];
for (int i=tn;i;i--)s2[o[s1[i]&255]--]=s1[i];
memset(o,0,sizeof(o));
for (int i=1;i<=tn;i++)o[s2[i]>>8]++;
for (int i=1;i<256;i++)o[i]+=o[i-1];
for (int i=tn;i;i--){
int p=(o[s2[i]>>8]--)+tn2;
w[p]=col[t[p]=s2[i]];
}memset(o,0,sizeof(o));
for (int i=br-2;i>=bl;i--)w[i]+=w[i+1];
upd(k);
}
void chk(int k){
bool fl=vis[st[k][top[k]]];
while(vis[st[k][top[k]]])top[k]--;
if (fl)upd(k);
}
int qry(int x){
int k=x/BS,ret=max(st[k][top[k]],l[fir[x]].t);
return !ret ? a[x] : col[ret];
}
ll qry(int l,int r)
{
ll ret=0;
if (l/BS==r/BS){for (int i=l;i<=r;i++)ret+=qry(i);}
else {
int tl=l/BS,tr=r/BS;
for (int i=tl+1;i<tr;i++)ret+=sb[i];
for (int i=l;i<tl*BS+BS;i++)ret+=qry(i);
for (int i=tr*BS;i<=r;i++)ret+=qry(i);
}return ret;
}
void cov(int l,int r)
{
if (l/BS==r/BS){
for (int i=l;i<=r;i++)adl(i,tq);
build(l/BS);return ;
}
int tl=l/BS,tr=r/BS;
for (int i=tl+1;i<tr;i++)
sb[i]=1ll*col[st[i][++top[i]]=tq]*BS;
for (int i=l;i<tl*BS+BS;i++)adl(i,tq);
for (int i=tr*BS;i<=r;i++)adl(i,tq);
build(tl);build(tr);
}
void undo(int k)
{
vis[k]=1;int l=sl[k],r=sr[k];
if (l/BS==r/BS){pop(l/BS);build(l/BS);return ;}
int tl=l/BS,tr=r/BS;
for (int i=tl+1;i<tr;i++)chk(i);
pop(tl);build(tl);pop(tr);build(tr);
}
int n,m;
int main()
{
scanf("%d%d",&n,&m);
BS=min(0.4*sqrt(n*log(n))+1,403.0);
for (int i=0,x;i<n;i++)scanf("%d",&a[i]);
for (int k=0;k*BS<n;k++)build(k);
ll las=0;
for (int i=1,op,l,r,x;i<=m;i++){
scanf("%d",&op);
if (op==1){
tq++;
scanf("%d%d%d",&sl[tq],&sr[tq],&col[tq]);
sl[tq]=(sl[tq]^las)-1;sr[tq]=(sr[tq]^las)-1;
cov(sl[tq],sr[tq]);
}
if (op==2){
scanf("%d%d",&l,&r);l=(l^las)-1;r=(r^las)-1;
printf("%lld\n",las=qry(l,r));
}
if (op==3){scanf("%d",&x);undo(x^las);}
}return 0;
}
```