区间修改单点查询的主席树
改个差分就行了
首先强制在线的是查询
所以修改可以一次全读进来然后离散并且插进去 没有影响
这里的话先全修改完再查询 可以放弃树状数组直接维护差分
然后主席树维护区间数字个数和整体和
最后分到叶子节点的时候注意去对应个数个数字加进去就行
然后有个操作就是一次把所有这个点上的差分数组都加进去
不开long long ***
Code:
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<vector> 5 #include<algorithm> 6 #define rep(i,a,n) for(int i = a;i <= n;i++) 7 #define per(i,n,a) for(int i = n;i >= a;i--) 8 using namespace std; 9 typedef long long ll; 10 int read() { 11 int as = 0,fu = 1; 12 char c = getchar(); 13 while(c < '0' || c > '9') { 14 if(c == '-') fu = -1; 15 c = getchar(); 16 } 17 while(c >= '0' && c <= '9') { 18 as = as * 10 + c - '0'; 19 c = getchar(); 20 } 21 return as * fu; 22 } 23 const int N = 1000005; 24 const int M = 16000005; 25 //head 26 int n,Q,T; 27 int ls[M],rs[M],sze[M],sum[M]; 28 int tot,h[N],rt[N]; 29 void ins(int l,int r,int &t,int pre,int q,int v) { 30 t = ++tot,ls[t] = ls[pre],rs[t] = rs[pre]; 31 sze[t] = sze[pre] + v,sum[t] = sum[pre] + h[q] * v; 32 if(l == r) return; 33 int m = l+r >> 1; 34 if(q <= m) ins(l,m,ls[t],ls[pre],q,v); 35 else ins(m+1,r,rs[t],rs[pre],q,v); 36 } 37 38 int query(int l,int r,int t,int k) { 39 if(k <= 0) return 0; 40 if(k >= sze[t]) return sum[t]; 41 if(l == r) return sum[t] * k / sze[t]; 42 int m = l+r >> 1,ans = query(l,m,ls[t],k); 43 if(k > sze[ls[t]]) ans += query(m+1,r,rs[t],k - sze[ls[t]]); 44 return ans; 45 } 46 vector<int> a[N]; 47 int main() { 48 // freopen("in.in","r",stdin); 49 // freopen("a.out","w",stdout); 50 Q = read(),n = read(); 51 rep(i,1,Q) { 52 int x = read(),y = read(),z = read(); 53 a[x].push_back(z),a[y+1].push_back(-z); 54 h[i] = z; 55 } 56 sort(h+1,h+Q+1),T = unique(h+1,h+Q+1) - (h+1); 57 rep(i,1,n) { 58 rt[i] = rt[i-1]; 59 rep(j,0,(int)a[i].size() - 1) { 60 int k = (a[i][j] < 0 ? -1 : 1); 61 a[i][j] = max(a[i][j],-a[i][j]); 62 ins(1,T,rt[i],rt[i],lower_bound(h+1,h+T+1,a[i][j]) - h,k); 63 } 64 } 65 int ans = 1; 66 rep(i,1,n) { 67 ll x = read(),a = read(),b = read(),c = read(); 68 int k = (a * ans + b) % c + 1; 69 printf("%d ",ans = query(1,T,rt[x],k)); 70 } 71 return 0; 72 }