NKOJ3776 工资管理（树状数组）

发表于 |
字数统计: 940字 | 阅读时长 ≈ 5min

问题描述

何老板的公司有n名员工，编号1到n。一开始所有员工的工资都是0。根据何老板的心情好坏，可能出现下列两种针对员工工资的操作：
1.U x y 改工资操作：何老板将第x号员工的工资改成了y；
2.Z x y 减工资操作：何老板生气了，他想选出x个员工，并将他们的工资全都减去1。何老板想知道，他能否一口气进行y次这样的减工资操作。能输出TAK，否则输出NIE。注意，员工的工资不能为负。

对于每个减工资的操作，何老板只是在心里想想，口头上说说，吓唬吓唬大家，解解闷气，他并不会真正执行。即不会对任何人的工资进行修改。

输入格式

第一行包含两个正整数n,m，分别表示员工的人数和操作次数。
接下来m行，每行一个操作，形式如题面所述。

输出格式

包含若干行，对于每个减工资操作，若可行，输出TAK，否则输出NIE。

样例输入 1

3 8
U 1 5
U 2 7
Z 2 6
U 3 1
Z 2 6
U 2 2
Z 2 6
Z 2 1

样例输出 1

NIE
TAK
NIE
TAK

样例输入 2

13 17
U 1 12
Z 1 9
Z 1 5
Z 4 7
U 7 18
Z 1 1
Z 1 8
U 6 4
U 1 9
U 3 13
Z 5 2
U 7 8
U 4 20
U 7 14
Z 6 1
Z 3 2
Z 8 7

样例输出 2

TAK
TAK
NIE
TAK
TAK
NIE
NIE
TAK
NIE

提示

对于30%的数据：$1<=n,m<=1000$
对于100%的数据：$1<=n,m<=200000,1<=x<=n，0<=y<=10^9,1<=y<=10^9$

主要问题在操作2。
首先相当将工资大于等于y的人数记为c，那么现在问题变成工资小于y的人能否每次选出（x-c）个人来完成y次操作。
因为每个人工资是小于y的，如果剩下的人的工资总和不足 $y\times(x-c)$ 那么显然不行，如果剩下的人的工资总和大于 $y\times(x-c)$ ，那么剩下的人数显然大于x-c，考虑一下发现显然可行。因为如果某次操作后选不出x-c个人，而总和大于 $y\times(x-c)$那么就有人的工资大于y。

附上代码

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
#define N 1234567
using namespace std;
ll c[N],d[N];
ll ty[N],a[N],b[N],w[N],n,m;
ll v[N],tot,t;
void MDc(ll x,ll k)
{for(ll i=x;i<=tot;i+=(i&-i))c[i]+=k;}
void MDd(ll x,ll k)
{for(ll i=x;i<=tot;i+=(i&-i))d[i]+=k;}
ll GSc(ll x)
{
	ll i,sum=0;
	for(i=x;i>0;i-=(i&-i))sum+=c[i];
	return sum;
}
ll GSd(ll x)
{
	ll i,sum=0;
	for(i=x;i>0;i-=(i&-i))sum+=d[i];
	return sum;
}
int main()
{
	char s;ll i;
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=m;i++)
	{
		s=getchar();
		while(s!='U'&&s!='Z')s=getchar();
		scanf("%lld%lld",&a[i],&b[i]);
		if(s=='U')ty[i]=1;else ty[i]=2;
		v[++tot]=b[i];
	}
	sort(v+1,v+tot+1);
	for(i=1;i<=m;i++)b[i]=lower_bound(v+1,v+tot+1,b[i])-v;
	for(i=1;i<=m;i++)
	{
		if(ty[i]==1)
		{
			if(w[a[i]])MDc(w[a[i]],-1);
			MDc(b[i],1);
			if(w[a[i]])MDd(w[a[i]],-v[w[a[i]]]);
			MDd(b[i],v[b[i]]);
			w[a[i]]=b[i];
		}
		else
		{
			t=GSc(tot)-GSc(b[i]-1);
			if(t>=a[i])puts("TAK");
			else
			{
				if(GSd(b[i]-1)>=(a[i]-t)*v[b[i]])puts("TAK");
				else puts("NIE");
			}
		}
	}
}