[DS记录]P7447 [Ynoi2007] rgxsxrs
command_block
2021-06-28 21:29:13
**题意** ： 给定一个长为 $n$ 的序列 $A$ ，进行 $m$ 次操作 ：
- 将区间 $[l,r]$ 中所有 $>x$ 的元素减去 $x$。
- 表示询问区间 $[l,r]$ 的和，最小值，最大值。
$n,m\leq 5\times 10^5,A_i\leq 10^9$ ，时限$\texttt{6s}$ ，空限$\texttt{64M}$。
------------
我们认为 $O(\log n)=O(\log A)$。
考虑倍增分块，倍数为 $B$ ，将值域分为形如 $[B^i,B^{i+1})$ 的 $O(\log_Bn)$ 个块。
对于每个块内的数，分别用线段树维护。需要维护区间最小值最大值以及和。
对第 $i$ 棵线段树修改时，分三类讨论 ：
- ① $a_{\max}\leq x$ ： 操作没有影响，直接返回。
- ② $a_{\min}-x\geq B_i$ ： 区间内减 $x$ 后仍然都在当前块内，打区间减标记即可。
- ③ 对于叶节点，$a-x<B_i$ ：将其删除，加入下一层。
三类位置形成若干连续段，若段数为 $k$ ，则本次操作的复杂度为 $O(k\log n)$。
在 ③ 中，每个值只会下降 $O(\log_Bn)$ 次，这部分复杂度为 $O(n\log n\log_Bn)$。
其余的复杂度可以看做与 ② 的个数直接相关。
块内的总和至多是 $O(nB^{i+1})$ 的，每次修改中，若存在 ① 且 ② 生效 $k$ 次，则总和至少减少 $O(kB^i)$。
于是花费于 ② 的总复杂度是 $O(nB\log n)$ 的。
选取一个合适的 $B$ 可以做到 $O\big((n+m)\log^2n/\log\log n\big)$。
此时空间复杂度是 $O(n\log n/\log\log n)$ ，且常数较大，难以通过。
考虑底层进行 $O(\log)$ 分块，对小区间进行暴力，即可改进为 $O(n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 530000
using namespace std;
namespace io {
char buf[1<<22],*p1=buf,*p2=buf,obuf[5005000],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,(1<<22)-10,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 BS=16,INF=1000000000
,pw[9]={1,10,100,1000,10000,100000,1000000,10000000,100000000};
inline void glev(int x,int &p){while(pw[p]>x)p--;}
int x[MaxN],lev[MaxN],st[MaxN],tn,slv[MaxN];
struct Node{
int x0,x1,c,tg;ll s;
inline void ladd(int t)
{tg+=t;x0+=t;x1+=t;s+=1ll*t*c;}
};
int n,x0,x1;ll sum;
struct SGT{
int lv;
Node a[(MaxN/BS)<<1];
inline void up(int u){
a[u].x0=min(a[u<<1].x0,a[u<<1|1].x0);
a[u].x1=max(a[u<<1].x1,a[u<<1|1].x1);
a[u].s=a[u<<1].s+a[u<<1|1].s;
a[u].c=a[u<<1].c+a[u<<1|1].c;
}
inline void build2(int l,int r,int u)
{
a[u].x0=INF;a[u].x1=a[u].s=a[u].c=0;
for (int i=l;i<=r;i++){
if (lev[i]==-1&&slv[i]==lv)lev[i]=lv;
if (lev[i]==lv){
a[u].x0=min(a[u].x0,x[i]);
a[u].x1=max(a[u].x1,x[i]);
a[u].c++;a[u].s+=x[i];
}
}
}
void build(int l,int r,int u)
{
if (r-l+1<=BS){build2(l,r,u);return ;}
int mid=(l+r)>>1;
build(l,mid,u<<1);
build(mid+1,r,u<<1|1);
up(u);
}
inline void ladd(int u){
if (a[u].tg){
a[u<<1].ladd(a[u].tg);
a[u<<1|1].ladd(a[u].tg);
a[u].tg=0;
}
}
inline void ladd2(int l,int r,int u){
if (!a[u].tg)return ;
for (int i=l;i<=r;i++)
if (lev[i]==lv)x[i]+=a[u].tg;
a[u].tg=0;
}
int to;
void upd(int l,int r,int u)
{
if (r-l+1<=BS){ladd2(l,r,u);build2(l,r,u);return ;}
int mid=(l+r)>>1;ladd(u);
if (to<=mid)upd(l,mid,u<<1);
else upd(mid+1,r,u<<1|1);
up(u);
}
void upd(int t){to=t;upd(1,n,1);}
int wfl,wfr,wfc;
void _sub(int l,int r,int u)
{
if (r-l+1<=BS){
ladd2(l,r,u);
int tl=max(l,wfl),tr=min(r,wfr);
for (int i=tl;i<=tr;i++)if (lev[i]==lv&&x[i]>wfc){
glev(x[i]-=wfc,lev[i]);
if (lev[i]<lv)st[++tn]=i;
}build2(l,r,u);return ;
}
if (a[u].x1<=wfc)return ;
if (wfl<=l&&r<=wfr&&a[u].x0-wfc>=pw[lv])
{a[u].ladd(-wfc);return ;}
int mid=(l+r)>>1;ladd(u);
if (wfl<=mid)_sub(l,mid,u<<1);
if (mid<wfr)_sub(mid+1,r,u<<1|1);
up(u);
}
void sub(int l,int r,int x)
{wfl=l;wfr=r;wfc=x;_sub(1,n,1);}
void qry(int l,int r,int u)
{
if (r-l+1<=BS){
ladd2(l,r,u);
l=max(l,wfl);r=min(r,wfr);
for (int i=l;i<=r;i++)if (lev[i]==lv)
{x0=min(x0,x[i]);x1=max(x1,x[i]);sum+=x[i];}
return ;
}
if (wfl<=l&&r<=wfr){
x0=min(x0,a[u].x0);
x1=max(x1,a[u].x1);
sum+=a[u].s;
return ;
}int mid=(l+r)>>1;ladd(u);
if (wfl<=mid)qry(l,mid,u<<1);
if (mid<wfr)qry(mid+1,r,u<<1|1);
}
void qry(int l,int r)
{wfl=l;wfr=r;qry(1,n,1);}
}T[9];
int m;
int main()
{
n=rd();m=rd();
for (int i=1;i<=n;i++)
glev(x[i]=rd(),lev[i]=8);
for (int i=0;i<9;i++)
{T[i].lv=i;T[i].build(1,n,1);}
int las=0;
for (int i=1,op,l,r,x;i<=m;i++){
op=rd();l=rd()^las;r=rd()^las;
if (op==1){
x=rd()^las;
for (int k=0;k<=8;k++){
tn=0;T[k].sub(l,r,x);
for (int j=1;j<=tn;j++)
{slv[st[j]]=lev[st[j]];lev[st[j]]=-1;}
for (int j=1;j<=tn;j++){
int p=st[j];
T[slv[p]].upd(p);
}
}
}else {
x0=INF;x1=sum=0;
for (int k=0;k<=8;k++)T[k].qry(l,r);
print(sum);putc(' ');
print(x0);putc(' ');
print(x1);putc('\n');
las=sum&((1<<20)-1);
}flush();
}flush(1);
return 0;
}
```