GGAutomaton's Blog
0%

[POI2011]MET-Meteors

发表于 分类于 ，

给定一个环，每个节点有一个所属国家，k次事件，每次对[l,r]区间上的每个点点权加上一个值，求每个国家最早多少次操作之后所有点的点权和能达到一个值
https://www.luogu.org/problemnew/show/P3527

先简单介绍一下整体二分：
当询问可以二分答案，且多组询问可以离线的时候，可以考虑整体二分。
因为所有询问要一起二分答案，所以把操作分治成一小块一小块，相应的询问放到相应的小块判断可行性。

这道题十分特殊，所有询问都在修改后面，而且二分的就是操作时间，可以这么处理。
每一次计算出mid时刻每个国家已经收集的数量，把所有能够完成国家的放在左边，所有不能完成的国家放在右边。左边继续二分mid以下的时间，右边继续二分mid以上的时间。
判断能否完成，用树状数组朝着mid时刻暴力加减即可，不能清零。

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
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long LL;
LL c[300005];
vector<int> G[300005];
int L[300005],R[300005],val[300005];
int P[300005],ans[300005];
int q[300005],q1[300005],q2[300005];
int n,m,k,now=0;
inline int read() {
	int sum=0;char ch=0;
	while (ch>'9' || ch<'0') ch=getchar();
	while (ch>='0' && ch<='9') sum=sum*10+ch-'0',ch=getchar();
	return sum;
}
inline int lowbit(int x) {
	return x&-x;
}
inline void add(int x,int v) {
	for (;x<=m;x+=lowbit(x)) c[x]+=v;
}
inline LL query(int x) {
	LL tmp=0;
	for (;x>0;x-=lowbit(x)) tmp+=c[x];
	return tmp;
}
inline void update(int l,int r,int v) {
	if (l<=r) {
		add(l,v);add(r+1,-v);
	}
	else {
		add(1,v);add(r+1,-v);
		add(l,v);add(m+1,-v);
	}
}
void solve(int l,int r,int s,int t) {//lr流星雨区间 mid答案 st未解决的国家区间 
	if (s>t) return;
	if (l==r) {
		for (int i=s;i<=t;i++) ans[q[i]]=l;
		return;
	}
	int mid=(l+r)>>1;
	while (now<mid) now++,update(L[now],R[now],val[now]);
	while (now>mid) update(L[now],R[now],-val[now]),now--;
	int s1=0,s2=0;
	for (int i=s;i<=t;i++) {
		LL tmp=0;
		int x=q[i];
		for (int j=0;j<G[x].size();j++) {
			tmp+=query(G[x][j]);
			if (tmp>=P[x]) break;
		}
		if (tmp>=P[x]) q1[++s1]=x;
		else q2[++s2]=x;
	}
	for (int i=1;i<=s1;i++) q[s+i-1]=q1[i];
	for (int i=1;i<=s2;i++) q[s+s1+i-1]=q2[i];
	solve(l,mid,s,s+s1-1);
	solve(mid+1,r,s+s1,t);
}
int main() {
	n=read();m=read();
	for (int i=1;i<=m;i++) G[read()].push_back(i);
	for (int i=1;i<=n;i++) {
		P[i]=read();
		q[i]=i;
	}
	k=read();
	for (int i=1;i<=k;i++) {
		L[i]=read();R[i]=read();val[i]=read();
	}
	solve(1,k+1,1,n);
	for (int i=1;i<=n;i++) {
		if (ans[i]==k+1) printf("NIE\n");
		else printf("%d\n",ans[i]);
	}
	return 0;
}

学习资源：
https://www.cnblogs.com/fenghaoran/p/7436593.html