题解 P6749 【『MdOI R3』Yoshino】
skydogli
2020-08-11 15:29:02
既然还没加强数据，那我就来写 $O(m(n+v))$ 的题解了。
首先用树状数组 $O(n\log v)$ 算出初始答案以及每个位置前面数值比它大的数量 $cnt_i$
然后考虑对于每个修改怎么计算贡献。
首先，这个修改内部不产生贡献，所以我们要减去原区间的贡献再加上新区间的贡献即可。
不难发现新的区间的贡献很好计算，对于在这个区间前面的数，令 $tax_i$ 表示数值大于 $i$ 的位置的数量，全部统计一遍，差分后前缀和即可。而对于后面的数，我们只需要讨论它和这个新增的数值区间的关系，具体地，设新区间值域为 $[v_l,v_r]$ ，我们枚举区间后面的数 $a_i$:
- $a_i<v_l$ ，贡献为$v_r-v_l+1$
- $v_l\le a_i<v_r$，贡献为$v_r-a_i$
- $a_i\ge v_r$ 贡献为0
这样做的话每次修改是稳定 $n$ 次操作的的。
不过，这样子很难求出原区间的影响，因为原区间值域不一定连续。
但是好心的出题人把值域也给到了 $O(n)$ 级别，也就是我们每次可以对整个值域差分并求前缀和，所以直接像上面一样搞就行了，效率稍差，总体时间复杂度 $O(m(n+v))$ 。
另外，O3对暴力优化极大。
```cpp
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define MN 30005
int mx;
int n,m,a[MN],sum[MN],tax[MN],V[MN],fk[MN];
int Op[MN],L[MN],R[MN],X[MN];
void add(int x){
while(x<=mx){
sum[x]++;
x+=x&(-x);
}
}
int ask(int x){
int res=0;
while(x){
res+=sum[x];
x-=x&(-x);
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
int res=0;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
mx=max(mx,a[i]);
}
for(int i=1;i<=n;++i){
V[i]=i-1-ask(a[i]);
res+=V[i];
add(a[i]);
}
for(int i=1;i<=m;++i){
scanf("%d",&Op[i]);
if(Op[i]==1){
scanf("%d%d%d",&L[i],&R[i],&X[i]);
mx=max(mx,X[i]+R[i]-L[i]);
}
}
for(int i=1;i<=m;++i){
int op=Op[i],l,r,x;
if(op==1)l=L[i],r=R[i],x=X[i];
if(op==1){
int vl=x,vr=x+r-l;
for(int j=l;j<=r;++j){
tax[j+x-l]=0;
fk[a[j]]++;
a[j]=j+x-l;
res-=V[j];
}
tax[vr+1]=0;
for(int j=1;j<l;++j){
if(a[j]>vr)tax[vr]++;
else if(a[j]>=vl)tax[a[j]-1]++;
}
for(int j=vr;j>=vl;--j){
tax[j]+=tax[j+1];
V[l+j-vl]=tax[j];
// cerr<<"upd: "<<l+j-vl<<endl;
res+=tax[j];
}
for(int j=mx;j;--j)fk[j]+=fk[j+1];
for(int j=r+1;j<=n;++j){
res-=fk[a[j]+1];
V[j]-=fk[a[j]+1];
V[j]+=max(0,vr-max(vl-1,a[j]));
// cerr<<"?? "<<fk[a[j]+1]<<" "<<max(0,vr-max(vl-1,a[j]))<<endl;
res+=max(0,vr-max(vl-1,a[j]));
}
for(int j=0;j<=mx;++j)fk[j]=tax[j]=0;
}
else{
printf("%d\n",res);
}
//if(i==2)break;
}
return 0;
}
```