【整体二分+树状数组】Meteros

传送门:CodeVS4232

似乎是POI的题(CV上各地的题有很多啊,然而似乎没更新近几年的。。。)


首先把环拆成链,然后给每个国家所在的太空站建一个链。

然后进行整体二分,把所有国家放在一个集合里,然后对场数(即答案)进行二分,判断在这个场数内能否达标,达标则放入一个集合,不达标放入另一个,分治一下。

那么问题就转化为了统计各个国家有没有达标,用树状数组维护区间和,然后单点(实际是多点,多个空间站)查询。

然而开始写完T的一塌糊涂(说实话这数据真良心,34个点),然后发现我把空间站放在集合里,重复了好几次,然后改了还是T。估计是因为N与M同阶,差的不多,然后发现我用链来写集合,与别人似乎都不大一样,而且我是用一个指针来控制修(乱)改(搞)树状数组的范围的,似乎会重复(然而我并不觉得),反正就是常数大,最后加了胡乱剪枝(没错分治用剪枝)才卡过(刺激啊!!!)

至于怎么优化常数,还是以后再想吧(智力孤危)


以下代码(T了别怪我)

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
LL n,m,p,tot,ans,T;
LL l[300030],r[300030],c[300030],head[300030],f[300030];
LL a[600030],b[600030],nxt[600030],bit[600030];
struct edge{
LL v,next;
}e[600030];
void add(LL x,LL y){
tot++;
e[tot].v=y;
e[tot].next=head[x];
head[x]=tot;
}
bool query(LL x,LL y){
LL sum=0;
for (int i=head[x];i;i=e[i].next){
for (int j=e[i].v;j;j-=j&(-j))
sum+=bit[j];
if (sum>=y) break;
}
return sum>=y;
}
void ins(LL x,LL y){
if (r[x]<l[x]) r[x]+=m;
for (int i=l[x];i<=m*2-1;i+=i&(-i))
bit[i]+=c[x]*y;
for (int i=r[x]+1;i<=m*2-1;i+=i&(-i))
bit[i]-=c[x]*y;
}
void work(LL l,LL r,LL s){
if (s==0) return;
LL mid=(l+r)>>1;
while(T<mid){
T++;
ins(T,1);
}
while(T>mid){
ins(T,-1);
T--;
}
LL h1=0,h2=0,j=0;
for (int i=s;i;i=j){
j=nxt[i];
if (query(i,b[i]))
nxt[i]=h2,h2=i;
else
nxt[i]=h1,h1=i;
}
if (l==r){
for (int i=h2;i;i=nxt[i])
f[i]=l;
return;
}
work(mid+1,r,h1);
work(l,mid,h2);
}
int main(){
scanf("%lld%lld",&n,&m);
for (int i=1;i<=m;i++){
scanf("%lld",&a[i]);
add(a[i],i);
}
for (int i=m+1;i<m*2;i++){
a[i]=a[i-m];
add(a[i],i);
}
for (int i=1;i<=n;i++) scanf("%lld",&b[i]);
scanf("%lld",&p);
for (int i=1;i<=p;i++) scanf("%lld%lld%lld",&l[i],&r[i],&c[i]);
for (int i=n;i;i--) nxt[i]=i-1;
work(1,p,n);
for (int i=1;i<=n;i++)
if (f[i]==0) printf("NIE\n");
else printf("%lld\n",f[i]);
return 0;
}