WA，不知道哪里错了。

思路是将数列分块，块内排序。

#include<bits/stdc++.h>
#define MAXN 300010
#define MAXB 600
using namespace std;
int n, m, u, siz, tot;
int a[MAXN];
vector<int> block[MAXB];
int id_block(int i){ return (i - 1) / siz + 1; }
int main(){
    scanf("%lld%lld%lld",&n,&m,&u);
    siz = sqrt(n); tot = ceil(n * 1.0 / siz);
    for(int i = 1; i <= n; i++) scanf("%lld",&a[i]);
    for(int i = 1; i <= tot; i++){
        for(int j = (i - 1) * siz + 1; j <= i * siz && j <= n; j++){
            block[i].push_back(a[j]);
        }
    }
    for(int i = 1; i <= tot; i++) sort(block[i].begin(), block[i].end());
    while(m--){
        int l, r, v, p, k = 0;
        scanf("%lld%lld%lld%lld",&l,&r,&v,&p);
        int idl = id_block(l), idr = id_block(r), idp = id_block(p);
        if(idl == idr) for(int i = l; i <= r; i++){if(a[i] < v) k++;}
        else{
            for(int i = l; i <= idl * siz; i++) if(a[i] < v) k++;
            for(int i = (idr - 1) * siz; i <= r; i++) if(a[i] < v) k++;
        }
        for(int i = idl + 1; i < idr; i++) k += lower_bound(block[i].begin(), block[i].end(), v) - block[i].begin();
        int pos = 0, sizp = block[idp].size(), val = 1LL * u * k / (r - l + 1);
        for(int i = 0; i < sizp; i++){
            if(block[idp][i] == a[p]){ pos = i; break; }
        }
        block[idp][pos] = val;
        while(pos > 0 && block[idp][pos] < block[idp][pos - 1]) swap(block[idp][pos], block[idp][pos - 1]), pos--;
        while(pos < sizp - 1 && block[idp][pos] > block[idp][pos + 1]) swap(block[idp][pos], block[idp][pos + 1]), pos++;
        a[p] = val;
    }
    for(int i = 1; i <= n; i++) printf("%lld\n",a[i]);
    return 0;
}