根据题意，我们知道每个位置都是非负整数（你搞个负数只麻雀出来）……
于是当两个区间互相包含时，小的区间是没用的。
所以至多有 \(n\) 个区间，我们按照它们的左端点来维护。
我们用线段树来维护每个左端点对应的最大右端点的区间，以及它的区间和。
对于第一个操作，在线段树上二分找包含这个点的最靠左的区间。
然后把它的左端点到修改点这一段全部加 \(y\)（不必考虑没有贡献的区间，它们对答案没有影响）。
对于第二个操作，直接塞进线段树。
同时用一个树状数组维护区间和。
代码： 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
96
using namespace std;
const int N = 5e5;
int n,m,c[N + 5];
inline void update(int x,int k)
{
for(;x <= n;x += lowbit(x))
c[x] += k;
}
inline int query(int x)
{
int ret = 0;
for(;x;x -= lowbit(x))
ret += c[x];
return ret;
}
struct node
{
int max,val,tag;
int ls,rs;
} seg[(N << 2) + 10];
int rt,seg_tot;
inline void push(int p)
{
if(seg[p].tag)
{
if(!seg[p].ls)
seg[p].ls = ++seg_tot;
seg[seg[p].ls].val += seg[p].tag,seg[seg[p].ls].tag += seg[p].tag;
if(!seg[p].rs)
seg[p].rs = ++seg_tot;
seg[seg[p].rs].val += seg[p].tag,seg[seg[p].rs].tag += seg[p].tag;
seg[p].tag = 0;
}
}
void insert(int x,int k,int v,int &p,int tl,int tr)
{
if(!p)
p = ++seg_tot;
seg[p].max = max(seg[p].max,k),seg[p].val = max(seg[p].val,v);
if(tl == tr)
return ;
push(p);
int mid = tl + tr >> 1;
x <= mid ? insert(x,k,v,seg[p].ls,tl,mid) : insert(x,k,v,seg[p].rs,mid + 1,tr);
}
void update(int l,int r,int k,int &p,int tl,int tr)
{
if(!p)
p = ++seg_tot;
if(l <= tl && tr <= r)
{
seg[p].val += k,seg[p].tag += k;
return ;
}
push(p);
int mid = tl + tr >> 1;
l <= mid && (update(l,r,k,seg[p].ls,tl,mid),1);
r > mid && (update(l,r,k,seg[p].rs,mid + 1,tr),1);
seg[p].val = max(seg[seg[p].ls].val,seg[seg[p].rs].val);
}
int query(int x,int p,int tl,int tr)
{
if(tl == tr)
return tl;
push(p);
int mid = tl + tr >> 1;
if(seg[seg[p].ls].max >= x)
return query(x,seg[p].ls,tl,mid);
else
return query(x,seg[p].rs,mid + 1,tr);
}
int main()
{
freopen("sparrow.in","r",stdin),freopen("sparrow.out","w",stdout);
scanf("%d%d",&n,&m);
int op,x,y;
while(m--)
{
scanf("%d%d%d",&op,&x,&y);
if(op == 1)
{
update(x,y);
if(seg[rt].max >= x)
{
int l = query(x,rt,1,n);
update(l,x,y,rt,1,n);
}
}
else
insert(x,y,query(y) - query(x - 1),rt,1,n);
printf("%d\n",seg[rt].val);
}
}