动态开点线段树： 长度为N的序列 $A_1,...,A_n$，初始为0

对于T个查询：

1 a b v : $A_i+=v (a<=i<=b)$

2 a b : 求 $min(A_i (a<=i<=b))$

1<=n<=1e9 , 1<=T<=1e5 , 1<=v<=1e4

我的代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,T;
int lc[100001*64];
int rc[100001*64];
int s[100001*64];
int la[100001*64];
int a[100001*64];
int cnt;
int add_node()
{
	++cnt;
	lc[cnt]=rc[cnt]=s[cnt]=la[cnt]=0;
	return cnt;
}
void push_up(int p)
{
	s[p]=min(a[lc[p]],a[rc[p]]);
}
void push_down(int p,int l,int r)
{
	if(l==r||la[p]==0) return;
	if(lc[p]==0) lc[p]=add_node();
	a[lc[p]]+=la[p];
	la[lc[p]]+=la[p];
	
	if(rc[p]==0) rc[p]=add_node();
	a[rc[p]]+=la[p];
	la[rc[p]]+=la[p];
	la[p]=0;
}
void add(int &p,int l,int r,int L,int R,int x)
{
	if(L>r||R<l) return;
	if(p==0) p=add_node();
	if(L<=l&&r<=R) return a[p]+=x,la[p]+=x,void();
	push_down(p,l,r);
	int mid=(l+r)/2ll;
	add(lc[p],l,mid,L,R,x);
	add(rc[p],mid+1,r,L,R,x);
	push_up(p);
}
int ask(int &p,int l,int r,int L,int R)
{
	if(L>r||R<l) return 1e9;
	if(p==0) p=add_node();
	if(L<=l&&r<=R) return a[p];
	push_down(p,l,r);
	int mid=(l+r)/2ll;
	return min(ask(lc[p],l,mid,L,R),ask(rc[p],mid+1,r,L,R));
}
signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>T;
	cnt=1;
	while(T--)
	{
		int ox; cin>>ox;
		if(ox==1)
		{
			int x,y,z; cin>>x>>y>>z;
			int q=1; 
			add(q,1,n,x,y,z);
		}
		else
		{
			int x,y; cin>>x>>y;
			int q=1;
			cout<<ask(q,1,n,x,y)<<'\n';
		}/*for(int i=1;i<=cnt;i++) cout<<a[i]<<" ";
		cout<<endl;*/
	}
	
	return 0;
}

给组数据 in:

100 100
2 18 67
1 76 91 805
1 68 81 7778
2 36 58
2 37 58
1 16 49 5232
2 81 100
2 53 95
2 86 97
1 2 51 3978
2 1 34
2 48 73
1 14 40 4455
1 10 81 5326
1 94 100 8071
1 31 100 4455
2 10 64
1 46 98 8256
2 5 45
2 56 76
1 10 54 7431
1 23 88 213
1 83 95 8755
1 19 75 6048
2 79 95
1 55 77 5757
2 42 43
1 27 38 8985
2 55 73
1 51 100 4953
2 17 64
1 6 72 9600
2 26 46
1 40 45 8466
1 2 23 1388
1 92 99 5529
2 20 39
1 13 69 8466
2 40 48
1 34 62 8676
2 13 34
2 1 2
1 49 64 989
1 7 74 9076
1 5 43 2211
1 56 97 7334
1 33 70 5854
1 47 68 7989
2 52 99
1 30 45 1429
2 24 65
2 34 82
2 17 41
1 23 89 4173
1 4 42 6225
1 43 56 5361
1 6 80 6566
1 5 41 5895
2 42 82
2 40 47
2 31 43
1 35 81 5152
1 5 10 8492
1 71 96 3947
2 46 64
1 2 44 9732
2 90 97
2 29 68
1 49 51 3590
1 42 78 9321
1 3 33 288
1 40 84 3326
1 36 79 7843
1 49 62 9447
1 49 85 5095
2 59 86
2 14 53
1 82 88 193
1 9 35 7219
2 23 30
2 20 69
1 34 75 320
2 29 90
1 3 8 1410
1 70 83 9338
1 7 39 113
2 36 79
2 3 80
2 3 89
2 46 96
1 5 74 2624
1 41 87 118
1 50 100 2744
2 6 21
1 45 99 8857
1 28 63 9012
1 50 70 6639
2 23 58
2 84 89
2 29 30

out:

0
0
0
0
0
0
0
0
9304
3978
18037
13729
32683
30055
26422
42283
42283
59005
36189
0
23008
62036
26016
57163
30189
98711
99764
100207
38505
99218
42557
80637
102134
99136
38505
84560
16796
16796
38505
58409
104871
54279
122868