19暑假训练3-2

符位是这里占

Infinite Inversions 树状数组求逆序对 思维

有一个序列:1,2,3,……,n,n无限大。给q个交换,每次将某两个位置的数相互交换。问q个交换后的序列的逆序对

EX:

Input
2
4 2
1 4
Output
4

首先,将q个交换的数离散化并记录下交换后它们所在的位置,然后将这几个数按照交换后顺序单独提出来(假设它们是a[1~x])求逆序对,用树状数组解决。

但是一个交换过的数数不仅会对其它被操作的数产生逆序对,还会对那些没操作过的数产生逆序对。比如1,6交换,1和6还会分别对2~5产生逆序对。设所有的被操作数序列是a[1~x],被操作数a[i]原位置是a[i],现位置是a[j],而显然这些数也就是在区间(min(a[i],a[j]),max(a[i],a[j]))中所有没操作过的数(即未出现在序列a[1~x]中的数),所以要统计一下任意两个被操作数间有多少个未被操作的数。设b[1~x]a[1~x]从大到小排序后的结果,也就是为交换前的样子,sum[i]=sum[i-1]+b[i]-b[i-1]-1,然后被操作数对未操作数的答案就是sum[max(a[i],a[j])]-sum[min(a[i],a[j])]

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <bitset>
#include <set>
#include <cmath>
using namespace std;
const int maxn = 2e5+ 10;
typedef long long ll;
int h,w;
ll b[maxn];
vector<int> v;
int n;
void A(int pos,int val) {
while(pos <= v.size()) {
b[pos] += val;
pos += pos & (-pos);
}
}

ll Q(int pos) {
ll ans = 0;
while(pos) {
ans += b[pos];
pos -= pos & (-pos);
}
return ans;
}

set<int> p;
int getp(int val) {
return lower_bound(v.begin(),v.end(),val) - v.begin() + 1;
}
ll sum[maxn];
int main() {
int n;
map<int,int> pos;
scanf("%d",&n);
while(n--) {
int a,b; scanf("%d%d",&a,&b);
if(!pos[a]) pos[a] = a;
if(!pos[b]) pos[b] = b;
swap(pos[a],pos[b]);
p.insert(pos[a]);
p.insert(pos[b]);
}
ll ans = 0;
for(auto it = p.begin(); it != p.end(); ++it)
v.push_back(*it);
for(int i = 1; i < v.size(); ++i)
sum[i + 1] = sum[i] + v[i] - v[i - 1] - 1;
int cnt = 1;
for(auto &i:pos) {
A(getp(i.second),1);
ans += cnt - Q(getp(i.second));
ans += sum[max(getp(i.second),cnt)] - sum[min(getp(i.second),cnt)];
++cnt;
}
printf("%lld\n",ans);
}

D-query 树状数组 离线处理

给定一段序列,q个询问任意一段的不重复数字的数量。

离线处理,先统计每个数依次出现的位置,然后对询问按照区间左端点排序。对于对于连续的一段相同数字1,1,1,1……对于左端点在第一个1位置(假设是L1)的查询,只需要在第一个1出现位置+1就好,其它数字以此类推,当所有L1左端点的查询结束后,设下一个查询左端点是L2,处理所有(L1,L2)区间里的数字,将它们此位置的1减掉,再在下一个>=L2的位置+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

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
const int maxn = 3e4 + 10;
typedef long long ll;
int b[maxn],a[maxn];
struct Query {
int l,r;
int res;
int rank;
};
int n;
bool operator<(const Query& a,const Query& b) {
return a.l < b.l;
}
bool byRank(const Query &a, const Query &b) {
return a.rank < b.rank;
}
void A(int pos,int val) {
while(pos <= n) {
b[pos] += val;
pos += pos & (-pos);
}
}
int Q(int pos) {
int ans = 0;
while(pos) {
ans += b[pos];
pos -= pos & (-pos);
}
return ans;
}
int main() {
scanf("%d",&n);
map<int,queue<int> > pos;
set<int> exist;
for(int i = 1; i <= n; ++i) {
scanf("%d",&a[i]);
pos[a[i]].push(i);
if(!exist.count(a[i])) {
A(i,1);
exist.insert(a[i]);
}
}
int q; scanf("%d",&q);
vector<Query> v;
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(int i = 0,nowl = 1; i < v.size(); ++i) {
while(nowl < v[i].l) {
while(pos[a[nowl]].size() && pos[a[nowl]].front() < v[i].l)
pos[a[nowl]].pop();
if(pos[a[nowl]].size()) {
A(pos[a[nowl]].front(),1);
}
++nowl;
}
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("%d\n",v[i].res);
}
}

Count Color 线段树 位运算表示集合

就是给一段区间,任意子区间染不超过30种颜色,询问任意子区间的颜色种数。因为不超过30所以可以用位表示所染颜色的集合,这样集合并也就成了按位或,没啥意思。

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <bitset>
#include <set>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
bitset<32> b[maxn<<2];
int lzy[maxn<<2];
void build(int o,int l,int r) {
if(l == r) { b[o].reset(); b[o][1] = 1; lzy[o] = 0; return; }
int mid = (l+r)>>1;
build(o*2,l,mid);
build(o*2+1,mid+1,r);
b[o].reset();
b[o][1] = 1;
lzy[o] = 0;
}

void pushdown(int o) {
if(lzy[o]) {
lzy[o*2] = lzy[o*2+1] = lzy[o];
b[o*2] = b[o*2+1] = b[o];
lzy[o] = 0;
}
}
void pushup(int o) {
b[o] = b[o*2] | b[o*2+1];
}
void A(ll o,int l,int r,int ql,int qr,int val) {
if(l >= ql && r <= qr) {
b[o].reset();
b[o][val] = 1;
lzy[o] = val;
return;
}
int mid = (l+r)>>1;
pushdown(o);
if(ql <= mid)
A(o*2,l,mid,ql,qr,val);
if(qr > mid)
A(o*2+1,mid+1,r,ql,qr,val);
pushup(o);
}
bitset<32> Q(int o,int l,int r,int ql,int qr) {
if(l >= ql && r <= qr)
return b[o];
pushdown(o);
bitset<32> ans;
int mid = (l+r)>>1;
if(ql <= mid)
ans |= Q(o*2,l,mid,ql,qr);
if(qr > mid)
ans |= Q(o*2+1,mid+1,r,ql,qr);
//sl.insert(sr.begin(),sr.end());
return ans;
}
int main() {
int l,t,o;
scanf("%d%d%d",&l,&t,&o);
build(1,1,l);
for(int i = 1; i <= o; ++i) {
char s[3];
int a,b,c;
scanf("%s%d%d",s,&a,&b);
if(a > b) swap(a,b);
if(s[0] == 'C') {
scanf("%d",&c);
A(1,1,l,a,b,c);
} else {
printf("%d\n",Q(1,1,l,a,b).count());
}
}
}

Can you answer these queries? 线段树 开方运算 剪枝

给一段区间,任意子区间中每个数开方(取整)or询问和。

本来以为是搞数学公式,结果就是不加lzytag直接递归到叶子节点然后开方,有个剪枝就是如果这个区间里每个数都<=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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <bitset>
#include <set>
#include <cmath>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
ll a[maxn];
ll b1[maxn<<2];
void pushup(int o) {
b1[o] = b1[o*2] + b1[o*2+1];
}
void build(int o,int l,int r) {
if(l == r) { b1[o] = a[l]; return; }
int mid = (l+r)>>1;
build(o*2,l,mid);
build(o*2+1,mid+1,r);
pushup(o);
}

void A(ll o,int l,int r,int ql,int qr) {
if(b1[o] <= (r-l+1)) return;
if(l == r) {
b1[o] = sqrt(b1[o]);
return;
}
int mid = (l+r)>>1;
if(ql <= mid)
A(o*2,l,mid,ql,qr);
if(qr > mid)
A(o*2+1,mid+1,r,ql,qr);
pushup(o);
}
ll Q(int o,int l,int r,int ql,int qr) {
if(l >= ql && r <= qr)
return b1[o];
ll ans = 0;
int mid = (l+r)>>1;
if(ql <= mid)
ans += Q(o*2,l,mid,ql,qr);
if(qr > mid)
ans += Q(o*2+1,mid+1,r,ql,qr);
return ans;
}
int main() {
int n;
int cnt = 0;
while(~scanf("%d",&n)) {
printf("Case #%d:\n",++cnt);
for(int i = 1; i <= n; ++i)
scanf("%lld",&a[i]);
build(1,1,n);
int q; scanf("%d",&q);
while(q--) {
int t,x,y; scanf("%d%d%d",&t,&x,&y);
if(x > y) swap(x,y);
if(t == 0) {
A(1,1,n,x,y);
} else {
printf("%lld\n",Q(1,1,n,x,y));
}
}
puts("");
}
}

Billboard HDU2795 树状数组 二分

h*w(h,w<=1e9)的告示牌,贴n(<=2e5)次告示,每次贴1*wi的东西(横着帖),选位置首先会选最高的位置,然后在最高的那行选最靠左的位置。

根据样例画个图,发现可以把告示牌竖起来处理,这样每次贴就变成了单点处理了。然后线段树就维护1~h的最大值。怎样选每次都贴最左端?:查询时可以优先考虑左子树就行了,如果左子树的最大值满足要求,就优先返回左子树的答案。

但是我没这样写。假设1,2,1,4,3,5这个序列,max[1~1]=1,max[1~2]=2,max[1~3]=2,max[1~4]=4。很显然任意一个序列,区间[1~x]的max值随着x的增加而单调,所以可以二分右端点,求出第一个max值>=wi的,此时的右端点就是答案。

但是h太大,所以总区间长度是min(h,n)

代码里的区间是镜像求的,非常蛋疼

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <bitset>
#include <set>
#include <cmath>
using namespace std;
const int maxn = 2e5 + 10;
typedef long long ll;
int h,w;
ll b1[maxn<<2];
void pushup(int o) {
b1[o] = max(b1[o*2],b1[o*2+1]);
}
void build(int o,int l,int r) {
if(l == r) { b1[o] = w; return; }
int mid = (l+r)>>1;
build(o*2,l,mid);
build(o*2+1,mid+1,r);
pushup(o);
}

void A(ll o,int l,int r,int qd,ll val) {
if(l == r && l == qd) {
b1[o] -= val;
return;
}
int mid = (l+r)>>1;
if(qd <= mid)
A(o*2,l,mid,qd,val);
else
A(o*2+1,mid+1,r,qd,val);
pushup(o);
}
ll Q(int o,int l,int r,int ql,int qr) {
if(l >= ql && r <= qr)
return b1[o];
ll ans = 0;
int mid = (l+r)>>1;
if(ql <= mid)
ans = max(ans,Q(o*2,l,mid,ql,qr));
if(qr > mid)
ans = max(ans,Q(o*2+1,mid+1,r,ql,qr));
return ans;
}
int main() {
int cnt = 0;
int n;
while(~scanf("%d%d%d",&h,&w,&n)) {
int t = n;
n = min(n,h);
build(1,1,n);
while(t--) {
int x; scanf("%d",&x);
if(x > b1[1]) {
puts("-1");
continue;
}
int l = 1,r = n;
while(l < r) {
int mid = (l+r+1)>>1;
if(Q(1,1,n,mid,n) >= x) {
l = mid;
} else r = mid - 1;
}
printf("%d\n",n - l + 1);
A(1,1,n,l,x);
}
}
}