19-暑假训练-3-1

这里是符位占

敌兵布阵 分块

单点修改区间查询,用分块随便做了做

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 50100;
typedef long long ll;
ll ai[maxn],sum[maxn],add[maxn];
ll L[maxn],R[maxn],pos[maxn];
void change(int l,int r,ll d) {
int p = pos[l],q = pos[r];
if(p == q) {
for(int i = l; i <= r; ++i)
ai[i] += d;
sum[p] += d*(r - l + 1);
} else {
for(int i = p + 1; i <= q - 1; ++i)
add[i] += d;
for(int i = l; i <= R[p]; ++i) ai[i] += d;
for(int i = L[q]; i <= r; ++i) ai[i] += d;
sum[p] += d*(R[p] - l + 1);
sum[q] += d*(r - L[q] + 1);
}
}
ll q(int l,int r) {
int p = pos[l],q = pos[r];
ll ans = 0;
if(p == q) {
for(int i = l; i <= r; ++i)
ans += ai[i];
return ans + (r - l + 1)*add[p];
} else {
for(int i = p + 1; i < q; ++i)
ans += sum[i] + add[i]*(R[i] - L[i] + 1);
for(int i = l; i <= R[p]; ++i)
ans += ai[i];
for(int i = L[q]; i <= r; ++i)
ans += ai[i];
ans += add[p]*(R[p]-l+1) + add[q]*(r-L[q]+1);
return ans;
}
}
int main() {
int T; cin>>T;
int Case = 0;
while(T--) {
memset(sum,0,sizeof sum);
memset(add,0,sizeof(add));
printf("Case %d:\n",++Case);
int n; cin>>n;
for(int i = 1; i <= n; ++i)
scanf("%lld",&ai[i]);
int t = sqrt(n);
for(int i = 1; i <= t; ++i)
L[i] = (i - 1) * sqrt(n) + 1,R[i] = i * sqrt(n);
if(R[t] < n) ++t,L[t] = R[t - 1] + 1,R[t] = n;
for(int i = 1; i <= t; ++i)
for(int j = L[i]; j <= R[i]; ++j)
pos[j] = i,sum[i] += ai[j];
char s[10]; int l,r;
while(scanf("%s",s)&&s[0] != 'E') {
scanf("%d%d",&l,&r);
if(s[0] == 'Q') {
printf("%lld\n",q(l,r));
}
else if(s[0] == 'A') {
change(l,l,r);
} else {
change(l,l,-r);
}
}
}
}

Ultra-QuickSort 逆序对 树状数组 离散化

首先需要离散化元素,然后求逆序对:

把元素a[i]当做下标,在相应位置+1,然后逆序对个数=i之前a[1~i-1]>a[i]的个数=i-a[1~i-1]<=a[i]的个数,用树状数组搞定

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn = 501000;
typedef long long ll;
int n;
ll a[maxn];
ll b[maxn];
ll p[maxn];
int tail;
int getp(int val) {
return lower_bound(p + 1,p + tail,val) - p;
}
void add(int val,int pos) {
while(pos <= n) {
b[pos] += val;
pos += pos&(-pos);
}
}
ll query(int pos) {
ll ans = 0;
while(pos) {
ans += b[pos];
pos -= pos&(-pos);
}
return ans;
}
int main() {
while(~scanf("%d",&n)&&n) {
ll ans = 0;

for(int i = 1; i <= n; ++i) {
scanf("%lld",&a[i]);
p[i] = a[i];
b[i] = 0;
}
sort(p + 1,p + 1 + n);
tail = unique(p + 1,p + 1 + n) - p;
for(int i = 1; i <= n; ++i) {
int val = getp(a[i]);
add(1,val);
ans += i - query(val);
}
printf("%lld\n",ans);
}
}

Mayor’s posters 线段树 离散化

在一段区间中选一段子区间染色,染色会覆盖在该位置之前的颜色,整个区间一开始为空白的,问染色若干次后的一整段区间里一共有几种颜色。

对于染色操作可以倒序处理,这样的话只要当前要染色的区间里存在空白的,就说明这次染色到最后并没有被覆盖,ans+1,否则说明当前的区间被后来的染色区间覆盖了,ans+0

然后这种区间操作用线段树处理会比较方便。设cover[i]为当前区间是否被完全覆盖(还存不存在空白区间)。而因为如果当前cover[i]==1时可以直接返回,不需要再往下递归至该区间的子区间,而且该区间以及子区间的cover不会再更改了,所以并没有lazytag和pushdown操作,只需要在更新子区间后pushup更新一下当前区间的cover就行了。

当然依然需要对左右区间的端点离散化一下。

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn = 21000;
typedef long long ll;
int n;
int al[maxn],ar[maxn];
ll p[maxn];
int getp(int val) {
return lower_bound(p + 1,p + tail,val) - p;
}
bool cover[maxn<<2];
bool post(int o,int l,int r,int ql,int qr) {
if(cover[o]) return 0;
if(l >= ql && r <= qr) { return cover[o] = 1; }
int mid = (l+r)>>1;
bool res = 0;
if(ql<=mid) res|=post(o*2,l,mid,ql,qr);
if(qr>mid) res|=post(o*2+1,mid+1,r,ql,qr);
cover[o] = cover[o*2] & cover[o*2+1];
return res;
}
int main() {
int T; cin>>T;
while(T-- && scanf("%d",&n)) {
for(int i = 1; i <= n; ++i)
scanf("%d%d",&al[i],&ar[i]),
p[i] = al[i],p[i + n] = ar[i];
sort(p + 1,p + n * 2 + 1);
tail = unique(p + 1,p + n * 2 + 1) - p;
int ans = 0;
memset(cover,0,sizeof(cover));
for(int i = n; i; --i)
ans += post(1,1,tail - 1,getp(al[i]),getp(ar[i]));
printf("%d\n",ans);
}
}

Turing Tree 树状数组 离线处理

给定n个数,若干次询问[l~r]内不重复元素的和。

一开始想线段树套个set(可持久化线段树?),实际上可以离线处理。

把询问区间按照右端点排序,然后把1~r内的所有元素插入树状数组,就可以求出任意l~r的询问。但是这样必须要求插入元素不重复,所以每次记录一下插入该数的上一个位置,然后如果该数之前已被插入,就在之前那个位置上减掉该数,再在当前位置上插入,这样就保证了插入元素都是唯一的。

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <set>
using namespace std;
const int maxn = 31000;
typedef long long ll;
int n;
int a[maxn];
int p[maxn];
int tail = 0;
int getp(int val) {
return lower_bound(p + 1,p + tail,val) - p;
}
struct query {
int l,r;
ll res;
int rank;
};
bool operator<(const query& a,const query & b) {
return a.r < b.r;
}
bool byRank(const query& a,const query& b) {
return a.rank < b.rank;
}
ll b[maxn];
ll Q(int pos) {
ll ans = 0;
while(pos) {
ans += b[pos];
pos -= pos & (-pos);
}
return ans;
}
void A(int pos,ll val) {
while(pos <= n) {
b[pos] += val;
pos += pos & (-pos);
}
}
int main() {
int T; cin>>T;
while(T-- && scanf("%d",&n)) {
for(int i = 1; i <= n; ++i)
scanf("%d",&a[i]),p[i] = a[i],b[i] = 0;
sort(p + 1,p + 1 + n);
tail = unique(p + 1,p + 1 + n) - p;
int q; scanf("%d",&q);
vector<query> v;
map<int,int> lastpos;
for(int i = 1; i <= q; ++i) {
int l,r; scanf("%d%d",&l,&r);
v.push_back({l,r,0,i});
}
sort(v.begin(),v.end());
for(ll i = 0,now = 1; i < v.size(); ++i) {
while(now <= v[i].r) {
if(lastpos.count(getp(a[now]))) A(lastpos[getp(a[now])],-a[now]);
lastpos[getp(a[now])] = now;
A(now,a[now]);
++now;
}
v[i].res = Q(v[i].r) - Q(v[i].l - 1);
}
sort(v.begin(),v.end(),byRank);
for(int i = 0; i < v.size(); ++i)
printf("%lld\n",v[i].res);
}
}

Super Mario 树状数组 离线处理

给定n个数,每次询问某个区间里<=h的数字的数量,每次询问h都是不一样的。

首先这个题区间是从0开始的,所以要先把左右端点+1。

这当然可以离线处理。统计数量,可以先在所有<=h的元素的相应位置上+1,这样就能统计出任意区间中所有<=h的元素数量。所以把询问按照h从小到大排序,然后询问就行了。因为要从小到大的插入数字,所以把数字也从小到大排序一遍并记录原先的位置,方便插入。

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <set>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
int n;
int a[maxn];
int tail = 0;
struct query {
int l,r,h;
ll res;
int rank;
};
bool operator<(const query& a,const query & b) {
return a.h < b.h;
}
bool byRank(const query& a,const query& b) {
return a.rank < b.rank;
}
int b[maxn];
int Q(int pos) {
int ans = 0;
while(pos>0) {
ans += b[pos];
pos -= pos & (-pos);
}
return ans;
}
void A(int pos,int val) {
while(pos <= n) {
b[pos] += val;
pos += pos & (-pos);
}
}
struct wall {
int num;
int pos;
};
bool operator>(const wall &a, const wall &b) {
return a.num > b.num;
}
int main() {
int T; cin>>T;
int Case = 0;
int qq;
while(T-- && scanf("%d%d",&n,&qq)) {
memset(b,0,sizeof(b));
priority_queue<wall,vector<wall>,greater<wall> > q;
for(int i = 1; i <= n; ++i) {
int a; scanf("%d",&a);
q.push({a,i});
}
vector<query> v;
for(int i = 1; i <= qq; ++i) {
int l,r,h; scanf("%d%d%d",&l,&r,&h);
v.push_back({++l,++r,h,0,i});
}
sort(v.begin(),v.end());
for(ll i = 0; i < v.size(); ++i) {
while(q.size() && q.top().num <= v[i].h) {
wall t = q.top(); q.pop();
A(t.pos,1);
}
v[i].res = Q(v[i].r) - Q(v[i].l - 1);
}
sort(v.begin(),v.end(),byRank);
printf("Case %d:\n",++Case);
for(int i = 0; i < v.size(); ++i)
printf("%lld\n",v[i].res);
}
}

A Simple Problem with Integers 树状数组区间修改和查询区间和




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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <set>
using namespace std;
const int maxn = 1e5+10;
typedef long long ll;
int n;
ll b1[maxn],b2[maxn],a[maxn],sum[maxn];
ll Q(ll *arr,int pos) {
ll ans = 0;
while(pos) {
ans += arr[pos];
pos -= pos & (-pos);
}
return ans;
}
void A(ll* arr,int pos,ll val) {
while(pos <= n) {
arr[pos] += val;
pos += pos & (-pos);
}
}
// void C(int o,int l,int r,int ql,int qr,ll val) {
// if(l >= ql && r <= qr) {
// b[o] = val * (r - l + 1);
// lazy[o] = val;
// return;
// }
// int mid = (l + r) >> 1;
// if(lazy[o]) {
// lazy[o*2] = lazy[o*2+1] = lazy[o];
// b[o*2] = lazy[o] * (mid - l + 1);
// b[o*2+1] = lazy[o] * (r - mid);
// lazy[o] = 0;
// }
// if(ql <= mid) C(o*2,l,mid,ql,qr,val);
// if(qr > mid) C(o*2+1,mid+1,r,ql,qr,val);
// b[o] = b[o*2] + b[o*2+1];
// }
// void build(int o,int l,int r) {
// b[o] = lazy[o] = 0;
// if(r == l) {
// return;
// }
// int mid = (l+r)>>1;
// build(o*2,l,mid);
// build(o*2+1,mid+1,r);
// }
int main() {
int q;
scanf("%d%d",&n,&q);
for(int i = 1; i <= n; ++i) {
ll x; scanf("%lld\n",&x);
a[i] = x;
sum[i] = sum[i - 1] + x;
}
while(q--) {
char s[3];
int a,b;
ll c;
scanf("%s%d%d",s,&a,&b);
if(s[0] == 'C') {
scanf("%lld",&c);
A(b1,a,c),A(b1,b+1,-c);
A(b2,a,a*c),A(b2,b+1,-(b+1)*c);
} else {
printf("%lld\n",(sum[b] + (b + 1)*Q(b1,b) - Q(b2,b)) - (sum[a-1] + a*Q(b1,a-1) - Q(b2,a-1)));
}
}
}

City Day RMQ

随便练一下RMQ,好久没写了。

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <set>
using namespace std;
const int maxn = 1e5+10;
typedef long long ll;
int n;
int a[maxn],dmax[maxn][20],dmin[maxn][20];
int lg[maxn];
int Qmin(int l,int r) {
if(r < l) return 0x7f7f7f7f;
return min(dmin[l][lg[r-l+1]],dmin[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
int main() {
for(int i = 1; i < maxn; ++i)
lg[i] = log2(i);
int x,y;
scanf("%d%d%d",&n,&x,&y);
for(int i = 1; i <= n; ++i)
scanf("%d",&a[i]),dmin[i][0] = a[i];
int ans = 0;
for(int i = 1; i < 20; ++i) {
for(int j = 1; j + (1<<i) - 1 <= n; ++j) {
//dmax[i][j] = max(dmax[i][j - 1],dmax[i + 1<<(j-1)][j - 1]);
dmin[j][i] = min(dmin[j][i - 1],dmin[j + (1<<(i-1)) ][i - 1]);
}
}
for(int i = 1; i <= n; ++i) {
if((Qmin(max(i-x,1),i-1) > a[i]) && (Qmin(i+1,min(i+y,n)) > a[i])) {
ans = i;
break;
}
}
printf("%d\n",ans);
}