无聊来刷水题……
现在这种树套树模板题我 20min 就搞定了，起不到愉悦身心的效果。
显然的权值线段树套线段树模板。
第一层维护权值，第二层维护位置，这样查询就不用另外二分，而是可以直接在权值线段树上二分。
这个题意有点杀，注意是每个位置都维护一个多重集，支持插入。
如果是加上一个数估计得分块？
反正我不会做。
这样就很水了，如果整体二分的话就相当于把 BIT 换成线段树，区间打标记。
树套树维护方式也是类似的。
代码： 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
using namespace std;
const int N = 5e4;
int n,m;
struct segnode
{
long long sum,tag;
int ls,rs;
} seg[(N << 8) + 10];
struct node
{
int rt;
int ls,rs;
} tree[(N << 3) + 10];
int rt;
void update(int l,int r,int &p,int tl,int tr)
{
static int tot = 0;
if(!p)
p = ++tot;
seg[p].sum += min(r,tr) - max(l,tl) + 1;
if(l <= tl && tr <= r)
{
++seg[p].tag;
return ;
}
int mid = tl + tr >> 1;
if(l <= mid)
update(l,r,seg[p].ls,tl,mid);
if(r > mid)
update(l,r,seg[p].rs,mid + 1,tr);
}
long long query(int l,int r,int p,int tl,int tr)
{
if(!p || (l <= tl && tr <= r))
return seg[p].sum;
int mid = tl + tr >> 1;
long long ret = seg[p].tag * (min(r,tr) - max(l,tl) + 1);
if(l <= mid)
ret += query(l,r,seg[p].ls,tl,mid);
if(r > mid)
ret += query(l,r,seg[p].rs,mid + 1,tr);
return ret;
}
void update(int l,int r,int x,int &p,int tl,int tr)
{
static int tot = 0;
if(!p)
p = ++tot;
update(l,r,tree[p].rt,1,n);
if(tl == tr)
return ;
int mid = tl + tr >> 1;
x <= mid ? update(l,r,x,tree[p].ls,tl,mid) : update(l,r,x,tree[p].rs,mid + 1,tr);
}
int query(int l,int r,long long k,int p,int tl,int tr)
{
if(tl == tr)
return tl;
long long cnt = query(l,r,tree[tree[p].rs].rt,1,n);
int mid = tl + tr >> 1;
return k <= cnt ? query(l,r,k,tree[p].rs,mid + 1,tr) : query(l,r,k - cnt,tree[p].ls,tl,mid);
}
int main()
{
scanf("%d%d",&n,&m);
int op,l,r;
long long k;
while(m--)
{
scanf("%d%d%d%lld",&op,&l,&r,&k);
if(op == 1)
update(l,r,k,rt,-n,n);
else
printf("%d\n",query(l,r,k,rt,-n,n));
}
}