题目大意：
给定一个长度为n的序列和m次操作，每次操作设ans为在[l,r]中严格效益v的数的个数，将a[p]改为
（k∗ans）/（r−l+1）
题解：
可以将操作分为两步：
1.求ans
2.更改数值
分块，块内有序，便于查询ans，更改后与左右进行交换，保证块内有序。
例如，读入完所有的数，用一个bolck数组存下来，排序，就达到了块内有序的要求
for(int i=1;i<=n;i++)
{
scanf("%d",&b[(i-1)/block+1][++b[(i-1)/block+1][0]]);
a[i]=b[(i-1)/block+1][b[(i-1)/block+1][0]];
}
其次，查询。
如果l，r在一个块内，直接查整个块；否则，把两边的残余块先查了，中间的完整的块就直接lower_bound即可。
int getans(int l,int r,int v)//查询
{
int lk=(l-1)/block+1,rk=(r-1)/block+1,tot=0;
if(lk==rk)//在同一块
{
for(int i=l;i<=r;i++)
{
if(a[i]<v)
{
tot++;
}
}
}else{
for(int i=l;i<=lk*block;i++)//l所在的块
{
if(a[i]<v)
{
tot++;
}
}
for(int i=(rk-1)*block+1;i<=r;i++)//r所在的块
{
if(a[i]<v)
{
tot++;
}
}
for(int i=lk+1;i<rk;i++)//lower_bound查询
{
tot+=lower_bound(b[i]+1,b[i]+b[i][0]+1,v)-b[i]-1;
}
}
return tot;
}
更改：找到这个块，找到这个点（块内有序），更改，与左右的数交换，用以保证有序。
void change(int x,int y)//更改
{
if(a[x]==y)
{
return;
}
int xk=(x-1)/block+1,xx=a[x],wei=1;
a[x]=y;
while(b[xk][wei]<xx)
{
wei++;
}
b[xk][wei]=y;
if(y>xx)//交换
{
while(wei<b[xk][0]&&b[xk][wei+1]<b[xk][wei])
{
swap(b[xk][wei+1],b[xk][wei]);
wei++;
}
}else{
while(wei>1&&b[xk][wei-1]>b[xk][wei])
{
swap(b[xk][wei-1],b[xk][wei]);
wei--;
}
}
}
程序：
#include<bits/stdc++.h>
#define N 300010
using namespace std;
int block,a[N],b[550][550],n,m,k,sum,l,r,v,p;
int getans(int l,int r,int v)//查询
{
int lk=(l-1)/block+1,rk=(r-1)/block+1,tot=0;
if(lk==rk)//在同一块
{
for(int i=l;i<=r;i++)
{
if(a[i]<v)
{
tot++;
}
}
}else{
for(int i=l;i<=lk*block;i++)//l所在的块
{
if(a[i]<v)
{
tot++;
}
}
for(int i=(rk-1)*block+1;i<=r;i++)//r所在的块
{
if(a[i]<v)
{
tot++;
}
}
for(int i=lk+1;i<rk;i++)//lower_bound查询
{
tot+=lower_bound(b[i]+1,b[i]+b[i][0]+1,v)-b[i]-1;
}
}
return tot;
}
void change(int x,int y)//更改
{
if(a[x]==y)
{
return;
}
int xk=(x-1)/block+1,xx=a[x],wei=1;
a[x]=y;
while(b[xk][wei]<xx)
{
wei++;
}
b[xk][wei]=y;
if(y>xx)//交换
{
while(wei<b[xk][0]&&b[xk][wei+1]<b[xk][wei])
{
swap(b[xk][wei+1],b[xk][wei]);
wei++;
}
}else{
while(wei>1&&b[xk][wei-1]>b[xk][wei])
{
swap(b[xk][wei-1],b[xk][wei]);
wei--;
}
}
}
int main()
{
// freopen("1.txt","r",stdin);
scanf("%d%d%d",&n,&m,&k);
block=sqrt(n);
sum=(n/block)+(n%block?1:0);
for(int i=1;i<=n;i++)
{
scanf("%d",&b[(i-1)/block+1][++b[(i-1)/block+1][0]]);
a[i]=b[(i-1)/block+1][b[(i-1)/block+1][0]];
}
for(int i=1;i<=sum;i++)//排序
{
sort(b[i]+1,b[i]+b[i][0]+1);
}
while(m--)
{
scanf("%d%d%d%d",&l,&r,&v,&p);
int ans=getans(l,r,v);
change(p,(1ll*k*ans)/(r-l+1));
}
for(int i=1;i<=n;i++)
{
printf("%d\n",a[i]);
}
return 0;
}