全局操作区间查询——转前缀和+主席树维护

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134369593

https://www.luogu.com.cn/problem/P9388

场上疯狂想分块，降智了

发现全局修改，区间查询，可以考虑前缀和

现在考虑维护某个时间戳的前缀。

我们现在有初始前缀所有数和前 qq 次操作的所有数，我们要删掉前 qq 大的数。

发现有值域和操作顺序 / 位置两个限制，考虑可持久化

发现维护三个很难，我们就拆成两棵线段树，一棵是位置，一棵是操作顺序，线段树都是维护值域对应的值

那查询怎么办？发现我们线段树开始的值域，那两棵线段树上一起操作即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
#define ll long long
inline 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<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 500010
//#define M
//#define mo
int n, m, i, j, k, T;
ll s[N], S, sum, ans; 
int l, r, x, q, rt1[N], rt2[N]; 

struct node {
	int tot, ls[N*22], rs[N*22];
	int w[N*22]; 
	ll s[N*22]; 
	void build(int &k, int l, int r) {
		if(!k) k=++tot; 
		if(l==r) return ; 
		int mid=(l+r)>>1; 
		build(ls[k], l, mid); 
		build(rs[k], mid+1, r); 
	}
	void push_up(int k) {
		s[k]=s[ls[k]]+s[rs[k]]; 
		w[k]=w[ls[k]]+w[rs[k]]; 
	}
	void add(int &u, int v, int l, int r, int x) {
		if(!u) u=++tot; 
//		if(tot>=8000000) 
//		debug("%lld [%lld %lld] [%lld %lld] %lld %lld\n", u, l, r, ls[u], rs[u], x, tot); 
		if(l==r) return w[u]=w[v]+1, s[u]=s[v]+l, void(); 
		int mid=(l+r)>>1; 
		if(x<=mid) add(ls[u], ls[v], l, mid, x), rs[u]=rs[v]; 
		else add(rs[u], rs[v], mid+1, r, x), ls[u]=ls[v]; 
		push_up(u); 
	}
}Seg1, Seg2;

ll que(int u, int v, int l, int r, int q) {
//	printf("We go %d %d [%d %d] %d\n", u, v, l, r, q); 
	if(l==r) return q*l; 
	int mid=(l+r)>>1; 
	int lu=Seg1.ls[u], ru=Seg1.rs[u], lv=Seg2.ls[v], rv=Seg2.rs[v]; 
	if(Seg1.w[lu]+Seg2.w[lv]>=q) 
		return que(lu, lv, l, mid, q); 
	else return que(ru, rv, mid+1, r, q-Seg1.w[lu]-Seg2.w[lv]) + Seg1.s[lu]+Seg2.s[lv]; 
}

ll calc(int r) {
	ll S=sum+s[r]; 
//	debug("[%lld] %lld %lld\n", r, S, que(rt1[r], rt2[i], 1, n, i)); 
	return S-que(rt1[r], rt2[i], 1, n, i); 
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	T=read();
//	while(T--) {
//
//	}
	n=read(); q=read(); 
	Seg1.build(rt1[0], 1, n); Seg2.build(rt2[0], 1, n); 
	for(i=1; i<=n; ++i) {
		k=read(); Seg1.add(rt1[i], rt1[i-1], 1, n, k); 
		s[i]=s[i-1]+k; 
//		debug("> %lld\n", Seg1.tot); 
	}
	for(i=1; i<=q; ++i) {
		x=read(); l=read(); r=read(); sum+=x; 
		Seg2.add(rt2[i], rt2[i-1], 1, n, x); 
		ans=calc(r)-calc(l-1); 
//		debug(">> %lld %lld\n", calc(r), calc(l-1)); 
		printf("%lld\n", ans); 
	}
	return 0;
}