给一列数，每次询问 将 a[ pi ] 的值 更新为 li 到 ri 区间中小于 vi 的个数 * u / （r-l+1）；
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define ll long long const int M = 3e5 + 10, SIZE = 4096; int B[M/SIZE + 1][SIZE + 1], a[M], n; int read(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*=f; } int solve(int L, int R, int v){ int ret = 0; int bl = (L-1)/SIZE, br = (R-1)/SIZE; if(bl == br){ for(int i = L; i <= R; i++) ret += a[i] < v; return ret; } for(int i = L; i <= (bl+1) * SIZE; i++) ret += a[i] < v; for(int i = br*SIZE+1; i <= R; i++) ret += a[i] < v; for(int i = bl + 1; i < br; i++) ret += lower_bound(B[i] + 1, B[i] + 1 + SIZE, v) - B[i] - 1; return ret; } void add(int pos, int x){ if(a[pos] == x)return ; int w = (pos-1)/SIZE; int tt = 1; while(B[w][tt] != a[pos])tt++; a[pos] = x; B[w][tt] = x; while(tt < SIZE && B[w][tt] > B[w][tt+1]) swap(B[w][tt], B[w][tt+1]), tt++; while(tt > 1 && B[w][tt] < B[w][tt-1]) swap(B[w][tt], B[w][tt-1]), tt--; } int main(){ //freopen("c.in","r",stdin); //freopen("my.out","w",stdout); int n, m, u; scanf("%d%d%d", &n, &m, &u); int blo = 0, j = 0; for(int i = 1; i <= n; i++){ a[i] = read(); B[blo][++j] = a[i]; if(j == SIZE){j = 0, blo++;} } for(int i = 0; i < blo; i++) sort(B[i]+1, B[i]+1+SIZE); if(j) sort(B[blo]+1, B[blo]+1+j); while(m--){ int L = read(), R = read(), v = read(), p = read(); int k = solve(L, R, v); add(p, 1LL*u*k/(R-L+1)); //for(int i = 1; i <= n; i++)printf("%d ", a[i]);puts(""); } for(int i = 1; i <= n; i++) printf("%d ", a[i]); }
求区间众数；
// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; const int M = 50005; int cnt[M], a[M], len, n, m, b[M], f[205][205], c[205][M], place[M]; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void init(int x){ memset(cnt, 0, sizeof(cnt)); int ans = 0; for(int i = x * len + 1; i <= n; i++){ int bl = place[i]; cnt[a[i]]++; if(cnt[a[i]] > cnt[ans] || (cnt[a[i]] == cnt[ans] && a[i] < ans)) ans = a[i]; f[x][bl] = ans; } } int query(int lf, int rg){ int ans = 0, mx = 0; if(place[rg]) ans = f[place[lf]+1][place[rg]-1]; if(place[rg]) mx = c[place[rg]-1][ans] - c[place[lf]][ans]; bool fg = place[lf]+1 <= place[rg]-1; for(int i = lf; i <= min((place[lf]+1)*len, rg); i++){ int tt = ++cnt[a[i]]; if(fg) tt += (c[place[rg]-1][a[i]] - c[place[lf]][a[i]]); if(tt > mx || (tt == mx && a[i] < ans)) mx = tt, ans = a[i]; } if(place[lf] != place[rg]) for(int i = place[rg]*len + 1; i <= rg; i++){ int tt = ++cnt[a[i]]; if(fg) tt += (c[place[rg]-1][a[i]] - c[place[lf]][a[i]]); if(tt > mx || (tt == mx && a[i] < ans)) mx = tt, ans = a[i]; } for(int i = lf; i <= min((place[lf]+1)*len, rg); i++)cnt[a[i]] = 0; if(place[lf] != place[rg]) for(int i = place[rg]*len + 1; i <= rg; i++)cnt[a[i]] = 0; return ans; } int main(){ //freopen("c.in","r",stdin); //freopen("my.out","w",stdout); scanf("%d%d", &n, &m); len = sqrt(n + 0.5); for(int i = 1; i <= n; i++)a[i] = b[i] = read(); sort(b + 1, b + 1 + n); int tot = unique(b + 1, b + 1 + n) - b - 1; for(int i = 1; i <= n; i++){ a[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b; place[i] = (i - 1)/len; c[place[i]][a[i]] = ++cnt[a[i]]; } for(int i = 0; i <= place[n]; i++)init(i); for(int i = 1; i <= tot; i++) for(int j = 1; j <= place[n]; j++) if(!c[j][i]) c[j][i] = c[j - 1][i]; //for(int i=0;i<=place[n];i++)for(int j=0;j<=place[n];j++)printf("%d ", f[i][j]); int lst = 0, l, r; memset(cnt, 0, sizeof(cnt)); while(m--){ l = read(), r = read(); l = (l + lst - 1) % n + 1, r = (r + lst - 1) % n + 1; if(l > r)swap(l, r); lst = b[query(l, r)]; printf("%d ",lst); //printf("%d %d %d ", l, r, lst); } }