BZOJ 4378 Logistyka

发表于 | 更新于

Link

Solution

如果>s> s的数字有>c> c个，肯定是可以的 否则，设有tt个，那么有c−tc-t个1∗s1*s需要从剩下的≤s\le s的数字中取。总共要取s(c−t)s(c-t)个11，那只要这c−tc-t数字的和≥s(c−t)\ge s(c-t)即可 充分必要性显然

Tips

从最显然的特殊情况(>s> s)看起，有可能可以启发出分类讨论的大体思路，帮助解题。

Code

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
#include "lucida"

using std::sort;
using std::unique;
using std::lower_bound;
const int MAXN=1000000+11;
struct Opt {
	char c;
	int x,y;
}op[MAXN];
template <class T>
struct Bit {
	T *a;int n;
	Bit(int n):n(n) {
		a=(T*)malloc((n+1)*sizeof(T));
	}
	#define lowbit(x) (x & -x)
	void Add(int pos,T x) {
		for(;pos<=n;pos+=lowbit(pos))
			a[pos]+=x;
	}
	T Sum(int pos) {
		T res=0;
		for(;pos;pos-=lowbit(pos))
			res+=a[pos];
		return res;
	}
	T Sum(int l,int r) {
		return Sum(r)-Sum(l-1);
	}
	#undef lowbit
};
int main() {
//	freopen("input","r",stdin);
	static int a[MAXN],nums[MAXN];
	int n,m;is>>n>>m;
	for(int i=1;i<=m;++i) {
		is>>op[i].c>>op[i].x>>op[i].y;
		nums[i]=op[i].y;
	}
	nums[m+1]=0;
	sort(nums+1,nums+2+m);
	int nc=unique(nums+1,nums+2+m)-nums-1;
	Bit<int> cnt(nc);
	Bit<int64> sum(nc);
	for(int i=1;i<=n;++i)
		cnt.Add(1,1);
	for(int i=1;i<=m;++i) {
		int cp=lower_bound(nums+1,nums+1+nc,op[i].y)-nums;
		if(op[i].c=='U') {
			int pp=lower_bound(nums+1,nums+1+nc,a[op[i].x])-nums;
			cnt.Add(pp,-1);
			cnt.Add(cp,1);
			sum.Add(pp,-nums[pp]);
			sum.Add(cp,nums[cp]);//pp..
			a[op[i].x]=op[i].y;
		} else {
			int gc=cnt.Sum(cp,nc);
			int64 tol=sum.Sum(1,cp-1);
			int c=op[i].x;
			os<<((gc>=c || tol>=(1ll*c-gc)*op[i].y)?"TAK":"NIE")<<'\n';
		}
	}
	return 0;
}