教主的魔法

傳送門

這道題序列很長，但是操作數很少，然后也沒想到什么好的數據結構來維護，那就分塊吧。

感覺維護的過程很好想，修改的時候對于整個塊都在內的直接打標記，兩個零散的區間暴力重構，重新排序。查詢的時候，對于整塊的，直接在塊內lowerbound一下z-add[i]的位置，零散的話直接暴力計算即可。

復雜度O（ksqrt(n)logsqrt(n)）.注意數組別開小了……

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('\n')using namespace std;
typedef long long ll;
const int M = 2000005;
const int N = 2005;
const ll INF = 1e17+9;
const ll mod = 19260817;ll read()
{ll ans = 0,op = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') op = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ans *= 10;ans += ch - '0';ans %= mod;ch = getchar();}return ans * op;
}ll a[M],b[N][N],l[N],r[N],blo[M],add[N],n,m,B,cnt,g = 1,x,y,z;
char s[5];ll query(ll x,ll y,ll z)
{ll L = blo[x],R = blo[y],ans = 0;if(L == R){rep(i,x,y) if(a[i] + add[L] >= z) ans++;return ans;}rep(i,L+1,R-1){//rep(j,1,B) printf("%lld ",b[i][j]);enter;//printf("!%lld\n",z - add[i]);int d = lower_bound(b[i]+1,b[i]+B,z - add[i]) - b[i];//printf("#%d\n",d);if(d == B && b[i][d] < z - add[i]) continue;ans += B - d + 1;}rep(i,x,r[L]) if(a[i] + add[blo[i]] >= z) ans++;rep(i,l[R],y) if(a[i] + add[blo[i]] >= z) ans++;return ans;
}void modify(ll x,ll y,ll z)
{ll L = blo[x],R = blo[y],cur = 0;if(L == R){rep(i,x,y) a[i] += z;rep(i,l[L],r[L]) b[L][++cur] = a[i];sort(b[L]+1,b[L]+1+B);return;}rep(i,L+1,R-1) add[i] += z;rep(i,x,r[L]) a[i] += z;rep(i,l[R],y) a[i] += z;rep(i,l[L],r[L]) b[L][++cur] = a[i];sort(b[L]+1,b[L]+B+1),cur = 0;rep(i,l[R],r[R]) b[R][++cur] = a[i];sort(b[R]+1,b[R]+B+1);
}int main()
{n = read(),m = read(),B = sqrt(n);cnt = (n % B) ? n / B + 1 : n / B;rep(i,1,cnt) l[i] = r[i-1] + 1,r[i] = l[i] + B - 1;r[cnt] = n;rep(i,1,n) a[i] = read();rep(i,1,n){blo[i] = g;if(i == r[g]) g++;}rep(i,1,cnt){int cur = 0;rep(j,l[i],r[i]) b[i][++cur] = a[j];sort(b[i]+1,b[i]+B+1);}rep(i,1,m){scanf("%s",s);x = read(),y = read(),z = read();if(s[0] == 'A') printf("%lld\n",query(x,y,z));else modify(x,y,z);}return 0;
}

?