【树状数组 线段树】洛谷 P3586 LOG
2021-06-02 18:28:00 # ACM

—–

题链

题意：判断序列能否选择$c$个数字同时$-1$并执行$s$次，操作单点修改；

对于序列中$>=s$的数字，相当于那些数字就等于$s$，毕竟执行$s$次也不会把这些数字删成$0$；

结论就是把那些超过$s$的数字看作$s$，如果序列的总和$>=c*s$的话，就是可行的，否则不可行；

把每个数想象成不同颜色的楼房，比如 $7$ $9$ $3$ $2$ 表示四栋楼房高度，询问能否每次选择$3$个数字$-1$并执行$5$次，就是选择$3$栋楼房砍去最上层；

$7$ $9$ $3$ $2$ 转化为 $5$ $5$ $3$ $2$，因为每次都得选择$3$个不同颜色的楼房，不妨把颜色 $3$，$4$ 的楼房叠在一起，那么序列就变成 $5$ $5$ $5$，每次砍去最上层且最上层颜色都不同；

也就是说把后一栋楼房的高度叠到前一栋楼房上，最高高度是$s$，这样能保证每次选择都是$c$个不同颜色楼房；

所以序列总和$>=c*s$则可行；

–动态开点权值线段树

吸氧才过的最后一个点…

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm> 
#include <ctime>
#include <cmath>
#include <stdio.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define PI acos(-1.0)
#define eps 1e-8
#define Pair pair<double,double>
// notice
#define mod 998244353 
#define MAXN 1e9
#define MS 1000009

LL n,m;
LL a[MS];
struct node{
	int l,r;
	LL cnt,val;
}p[MS<<5];
int tot;
int root;

void push_up(int &rt){
	if(!p[rt].l && !p[rt].r){
		rt = 0;
	}
	else if(!p[rt].l){
		p[rt].cnt = p[p[rt].r].cnt;
		p[rt].val = p[p[rt].r].val;
	}
	else if(!p[rt].r){
		p[rt].cnt = p[p[rt].l].cnt;
		p[rt].val = p[p[rt].l].val;
	}
	else{
		p[rt].cnt = p[p[rt].l].cnt + p[p[rt].r].cnt;
		p[rt].val = p[p[rt].l].val + p[p[rt].r].val;
	}
}

void update(int &rt,int pos,int l,int r,LL val,int t){
	if(!rt) rt = ++tot;
	if(l == r){
		if(t){
			p[rt].cnt++;
			p[rt].val += val;
		}
		else{
			p[rt].cnt--;
			p[rt].val -= val;
		}
		if(p[rt].cnt == 0){
			rt = 0;
		}
		return;
	}
	int m = l+r>>1;
	if(m >= pos) update(p[rt].l,pos,l,m,val,t);
	else update(p[rt].r,pos,m+1,r,val,t);
	push_up(rt);
}

node get_cnt(int rt,int L,int R,int l,int r){
	if(!rt) return {0,0,0,0};
	if(L <= l && r <= R){
		return p[rt];
	}
	int m = l+r>>1;
	if(m < L) return get_cnt(p[rt].r,L,R,m+1,r);
	else if(m >= R) return get_cnt(p[rt].l,L,R,l,m);
	else{
		node ans;
		node t1 = get_cnt(p[rt].l,L,R,l,m);
		node t2 = get_cnt(p[rt].r,L,R,m+1,r);
		ans.cnt = t1.cnt + t2.cnt;
		ans.val = t1.val + t2.val;
		ans.l = p[rt].l;
		ans.r = p[rt].r;
		return ans;
	}
	
//	LL ans = 0;
//	if(m >= L) ans += get_cnt(p[rt].l,L,R,l,m);
//	if(m <  R) ans += get_cnt(p[rt].r,L,R,m+1,r);
//	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;i++) a[i] = -1;
	while(m--){
		char op;
		LL pos,val,c,s;
		cin >> op;
		if(op == 'U'){
			cin >> pos >> val;
			if(a[pos] != -1)
				update(root,a[pos],0,MAXN,a[pos],0);
			a[pos] = val;
			update(root,a[pos],0,MAXN,a[pos],1);
		}
		else if(op == 'Z'){
			cin >> c >> s;
			LL sum = p[root].val;
			node tt = get_cnt(root,s,MAXN,0,MAXN);
			sum -= tt.val;
			sum += tt.cnt*s;
			if(sum >= c*s){
				cout << "TAK\n";
			}
			else{
				cout << "NIE\n";
			}
		}
	}
	

	return 0;
}

–树状数组

把操作离线，数据离散化处理

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
97
98
99
100
101
102
//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm> 
#include <ctime>
#include <cmath>
#include <stdio.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define PI acos(-1.0)
#define eps 1e-8
#define Pair pair<double,double>
// notice
#define mod 998244353 
#define MAXN 1e9
#define MS 1000009

LL n,m;
LL a[MS],ta;
LL v[MS];
struct node{
	char op;
	LL x,y;
}b[MS];
struct nod{
	LL cnt,val;
}p[MS];

LL lowbit(LL x){
	return x&(-x);
}

void add(LL pos,LL val,LL t){
	for(;pos<=m;pos+=lowbit(pos)){
		if(t){
			p[pos].cnt++;
			p[pos].val += val;
		}
		else{
			p[pos].cnt--;
			p[pos].val -= val;
		}
	}
}

nod query(LL pos){
	nod ans = {0,0};
	for(;pos;pos-=lowbit(pos)){
		ans.cnt += p[pos].cnt;
		ans.val += p[pos].val;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		char op;
		LL x,y;
		cin >> op >> x >> y;
		b[i] = {op,x,y};
		a[i] = y;
	}
	sort(a+1,a+m+1);
	ta = 1;
	for(int i=2;i<=m;i++){
		if(a[i] != a[i-1]) a[++ta] = a[i];
	}
	for(int i=1;i<=m;i++) v[i] = -1;
	for(int i=1;i<=m;i++){
		node t = b[i];
		if(t.op == 'U'){
			LL pos;
			if(v[b[i].x] != -1){
				pos = lower_bound(a+1,a+ta+1,v[b[i].x]) - a;
				add(pos,v[b[i].x],0);
			}
			v[b[i].x] = b[i].y;
			pos = lower_bound(a+1,a+ta+1,v[b[i].x]) - a;
			add(pos,v[b[i].x],1);
		}
		else{
			nod sum = query(m);
			LL pos = lower_bound(a+1,a+ta+1,b[i].y) - a;
			nod tt = query(pos-1);
			LL cc = tt.val + (sum.cnt-tt.cnt)*b[i].y;
			if(cc >= b[i].x*b[i].y){
				cout << "TAK\n";
			}
			else{
				cout << "NIE\n";
			}
		}
	}
	
	

	return 0;
}

Prev
2021-06-02 18:28:00 # ACM
Next