「cdqzD10T1」大型演习 - cdq分治+主席树维护单调栈 | Bill Yang's Blog

「cdqzD10T1」大型演习 - cdq分治+主席树维护单调栈

题目大意


题目分析

如果去掉若当前舰娘$i$发现有两个实力比自己小的目标$u,v$,其中$u$进入演习的时间比$v$早,而$u$的实力值比$v$小,那么$i$将不会在$S_i$中记录$u$这个条件,不难发现这就是一个简单的三维偏序问题。
如果加上这个条件,我们在如下图的一个平面内考虑:

该条件也就是限制若$a$点要对$b$点作出贡献,其围成的矩形中不能有其他的点。

考虑cdq分治,在位置序的基础上对$S$维进行分治。
考虑$S\lt mid$部分对$S\ge mid$部分做出的贡献。
不难发现对于每一个$mid$上方部分的点$p$,其得到的贡献一定来自于$mid$下方部分构成的单调递减栈$Sl[]$($Sl[]$中元素的位置需小于$p$的位置)。

同时我们也要考虑$p$被$mid$上方点遮挡的情况。
因此我们需要维护两个单调栈。

如图,我们在加入点的时候动态维护单调栈,对于$mid$上方的点$p$,$p$与其上一个单调栈中元素在$mid$下方夹出的区间即为可以贡献答案的部分,考虑使用某种数据结构进行维护。

我们要求这个数据结构支持的操作为:

  • 加入一个点维护单调栈
  • 统计单调栈中$T$值小于$x$的权值和。

我们可以使用主席树来维护(可持久化树状数组也行)。
注意主席树空间开大点,如果每次弹栈回收内存就可以开小些。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=50005;
struct President_Tree {
struct Tree {
int ls,rs,sum;
} tree[maxn*200];
int step;
int insert(int pre,int left,int right,int pos,int delta) {
int now=++step;
tree[now]=tree[pre];
tree[now].sum+=delta;
if(left==right)return now;
int mid=(left+right)>>1;
if(pos<=mid)tree[now].ls=insert(tree[pre].ls,left,mid,pos,delta);
else tree[now].rs=insert(tree[pre].rs,mid+1,right,pos,delta);
return now;
}
int query(int now,int left,int right,int target) {
if(left>target)return 0;
if(right<=target)return tree[now].sum;
int mid=(left+right)>>1;
return query(tree[now].ls,left,mid,target)+query(tree[now].rs,mid+1,right,target);
}
} pt;
struct Point {
int s,t,w;
int pos;
bool operator < (const Point& b) const {
return pos<b.pos;
}
} p[maxn],tmp[maxn];
int n,Ans[maxn],a[maxn],b[maxn],topl,topr,Sl[maxn],Sr[maxn],root[maxn];
int find(int v) {
int Left=1,Right=topl;
while(Left<=Right) {
int mid=(Left+Right)>>1;
if(p[Sl[mid]].pos<v)Left=mid+1;
else Right=mid-1;
}
return Right;
}
void CDQBinary(int Left,int Right) {
if(Left==Right)return;
int mid=(Left+Right)>>1,lpos=Left,rpos=mid+1;
for(int i=Left; i<=Right; i++)
if(p[i].s<=mid)tmp[lpos++]=p[i];
else tmp[rpos++]=p[i];
for(int i=Left; i<=Right; i++)p[i]=tmp[i];
CDQBinary(Left,mid);
lpos=Left;
topl=topr=0;
for(int i=mid+1; i<=Right; i++) {
while(lpos<=mid&&p[i].pos>p[lpos].pos) {
while(topl&&p[lpos].s>p[Sl[topl]].s)topl--;
Sl[++topl]=lpos;
root[topl]=pt.insert(root[topl-1],1,n,p[lpos].t,p[lpos].w);
lpos++;
}
while(topr&&p[i].s<p[Sr[topr]].s)topr--;
if(topl)Ans[p[i].pos]+=pt.query(root[topl],1,n,p[i].t)-pt.query(root[find(p[Sr[topr]].pos)],1,n,p[i].t);
Sr[++topr]=i;
}
CDQBinary(mid+1,Right);
merge(p+Left,p+mid+1,p+mid+1,p+Right+1,tmp);
int tot=0;
for(int i=Left; i<=Right; i++)p[i]=tmp[tot++];
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
a[i]=p[i].s=Get_Int();
b[i]=p[i].t=Get_Int();
p[i].w=Get_Int();
p[i].pos=i;
}
sort(a+1,a+n+1);
sort(b+1,b+n+1);
int acnt=unique(a+1,a+n+1)-a-1,bcnt=unique(b+1,b+n+1)-b-1;
for(int i=1; i<=n; i++) {
p[i].s=lower_bound(a+1,a+acnt+1,p[i].s)-a;
p[i].t=lower_bound(b+1,b+bcnt+1,p[i].t)-b;
}
CDQBinary(1,n);
for(int i=1; i<=n; i++)printf("%d\n",Ans[i]);
return 0;
}
本篇文章有用吗?有用还不快点击!
0%