> 这个比较漂亮
```cpp
#include <cstdio>
#define Lowbit(x) ((x) & -(x))
#define border 50001
#define inc(a) ++a
using namespace std;
int place[50001][50],num[51000][6],copy1[51000][6],copy2[51000][6],ans[51000],a[51000];
int tree[880000];
int n,m,l,r,x,y,k,cnt,ques,order;
void read() {
int ret=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
int Query(int x){
if (x<=0) return 0; int sum=0;
for(;x;x-=Lowbit(x)) sum+=tree[x];
return sum;
}
void Insert(int x,int k){
if (x<=0) return;
for(;x<=n;x+=Lowbit(x)) tree[x]+=k;
}
void Divid(int l,int r,int left,int right){
if (l>r or left>right) return;
if (l==r) {
for(int i=left;i<=right;i++) if (num[i][5]==1) ans[num[i][4]]=l;
return;
}
int mid=(l+r) >> 1,tot[2]; tot[1]=0; tot[2]=0;
for(int i=left;i<=right;inc(i)){
if (num[i][5]==1){
int tmp=Query(num[i][2])-Query(num[i][1]-1);
if (tmp>=num[i][3]){
inc(tot[1]); for(int j=1;j<=5;inc(j)) copy1[tot[1]][j]=num[i][j];
} else {
num[i][3]-=tmp;
inc(tot[2]); for(int j=1;j<=5;inc(j)) copy2[tot[2]][j]=num[i][j];
}
} else {
if (num[i][1]<=mid){
inc(tot[1]); for(int j=1;j<=5;inc(j)) copy1[tot[1]][j]=num[i][j];
Insert(num[i][4],num[i][2]);
} else {
inc(tot[2]); for(int j=1;j<=5;inc(j)) copy2[tot[2]][j]=num[i][j];
}
}
}
for(int i=1;i<=tot[1];inc(i)) if (copy1[i][5]==0) Insert(copy1[i][4],-copy1[i][2]);
for(int i=1;i<=tot[1];inc(i)) for(int j=1;j<=5;inc(j)) num[left+i-1][j]=copy1[i][j];
for(int i=1;i<=tot[2];inc(i)) for(int j=1;j<=5;inc(j)) num[left+tot[1]+i-1][j]=copy2[i][j];
Divid(l,mid,left,left+tot[1]-1);
Divid(mid+1,r,left+tot[1],right);
}
int main(){
n:=read(); m:=read(); ques=0;
for(int i=1;i<=n;inc(i)){
a[i]:=read();
inc(place[a[i]][0]);
place[a[i]][place[a[i]][0]]=i;
inc(cnt); num[cnt][1]=a[i]; num[cnt][2]=1; num[cnt][4]=i;
}
for(int i=1;i<=m;inc(i)){
order:=read();
if (order==2){
l:=read(); r:=read(); k:=read();
inc(ques);
inc(cnt); num[cnt][1]=l; num[cnt][2]=r;
num[cnt][3]=k; num[cnt][4]=ques; num[cnt][5]=1;
}
if (order==1){
l:=read(); r:=read(); x:=read(); y:=read();
for(int j=1;j<=place[x][0];inc(j))
if (place[x][j]>=l and place[x][j]<=r){
inc(cnt); num[cnt][1]=x; num[cnt][2]=-1; num[cnt][4]=place[x][j];
inc(cnt); num[cnt][1]=y; num[cnt][2]= 1; num[cnt][4]=place[x][j];
a[place[x][j]]=y;
inc(place[y][0]);
place[y][place[y][0]]=place[x][j];
place[x][j]=-1;
}
}
printf("%d %d\n",i,cnt);
}
//for(int i=1;i<=cnt;inc(i)) printf("%d %d %d %d %d %d\n",i,num[i][1],num[i][2],num[i][3],num[i][4],num[i][5]);
//printf("%d \n",cnt);
for(int i=1;i<=cnt;inc(i)) printf("%d %d",num[i][1],num[i][2]);
/*Divid(0,border,1,cnt);
for(int i=1;i<=ques;inc(i)) printf("%d\n",ans[i]);*/
return 0;
}
```
by arfa @ 2018-12-12 13:27:06
> 还是看第一个,下面那个编错
by arfa @ 2018-12-12 13:35:00
这题有log解法的吗？
惊了惊了
by shadowice1984 @ 2018-12-12 13:55:03
> @[shadowice1984](/space/show?uid=56384) 不是啊,如果数据不随机就不行。在数据随机的情况下,每一个数字的出现次数均为 $\frac{N}{num}$ 也就是 $1$,所以每一次修改只需要存储下来,次数约为 $1$(玄学复杂度)。然后我们考虑单点修改,区间查询第 $K$ 大可以用整体二分。时间复杂度为 $O((M\times $玄学$+N \log^2 num))$。如果不随机那就变成 $O((M+N^2) \log^2 num)$ 了,不过看来数据还是不随机的。
by arfa @ 2018-12-12 17:35:31
@[arfa](/space/show?uid=77760)
ynoi不可能有随机数据
by shadowice1984 @ 2018-12-12 18:57:38
别天天想着随机数据过题
ODT这种东西让我见识到了随机数据的脆弱
by noip @ 2019-02-16 13:26:18
捉
by 许多 @ 2022-07-16 17:54:09