[POI2015] LOG
题目描述
维护一个长度为 \(n\) 的序列，一开始都是 \(0\)，支持以下两种操作：
U k a将序列中第 \(k\) 个数修改为 \(a\)。Z c s在这个序列上，每次选出 \(c\) 个正数，并将它们都减去 \(1\)，询问能否进行 \(s\) 次操作。
每次询问独立，即每次询问不会对序列进行修改。
输入格式
第一行包含两个正整数 \(n,m\)，分别表示序列长度和操作次数。
接下来 \(m\) 行为 \(m\) 个操作。
输出格式
包含若干行，对于每个 Z 询问，若可行，输出 TAK，否则输出 NIE。
样例 #1
样例输入 #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
提示
【数据范围】
对于 \(100\%\) 的数据，\(1\leq n,m\leq 10^6\)，\(1\leq k,c\leq n\)，\(0\leq a\leq 10^9\)，\(1\leq s\leq 10^9\)。
原题名称：Logistyka。
解析
单点修改很好做，重点是如何维护查找操作。
最开始很容易想出来一个错误的思路，找他们总共的和是否大于 \(c \times s\) 。
但是，有一些数大于 \(s\) ，是不能做到 \(s\) 次的。
但是，一个数能贡献的价值只会有两个限制，一是它数本身的大小，二是 \(s\) ，所以单个数的贡献为 \(min(s,a_i)\) 。
分开统计，$a_i $ 大于 \(s\) 的直接让 \(c\) 减掉，小于 \(s\) 的统计和就好了。
我们只需要先做一遍离散化，然后开两个树状数组，一个统计每个位上有多少个数，用于做 \(a_i\) 大于 \(s\) 的情况，一个统计和，用于做第二种情况。
时间复杂度 \(O(mlogm)\)
Code
#include<bits/stdc++.h>
using namespace std;
struct datay
{
char x;
long long y,z;
}l[1000005];
long long n,m,a[1000005],f[1000005],d[1000005],p[1000005];
set<long long> q;
map<long long,long long> w;
long long lowbit(long long x)
{
return x&(-x);
}
void dijah1(long long x,long long y)
{
for(int i=x;i<=1000000;i+=lowbit(i))f[i]+=y;
return;
}
void dijah2(long long x,long long y)
{
for(int i=x;i<=1000000;i+=lowbit(i))d[i]+=y;
return;
}
long long gaia1(long long x)
{
long long h=0;
while(x)
{
h+=f[x];
x-=lowbit(x);
}
return h;
}
long long gaia2(long long x)
{
long long h=0;
while(x)
{
h+=d[x];
x-=lowbit(x);
}
return h;
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
{
cin>>l[i].x>>l[i].y>>l[i].z;
q.insert(l[i].z);
}
long long g=0;
set<long long>::iterator qw=q.begin();
for(;qw!=q.end();qw++)
{
w[*qw]=++g;
p[g]=*qw;
}
p[0]=0;
for(int i=1;i<=m;i++)l[i].z=w[l[i].z];
for(int i=1;i<=m;i++)
{
if(l[i].x=='U')
{
if(p[a[l[i].y]]!=0)dijah1(a[l[i].y],-p[a[l[i].y]]),dijah2(a[l[i].y],-1);
a[l[i].y]=l[i].z;
if(p[a[l[i].y]]!=0)dijah1(a[l[i].y],p[a[l[i].y]]),dijah2(a[l[i].y],1);
}
else
{
if(gaia1(l[i].z)>=(l[i].y-gaia2(1000000)+gaia2(l[i].z))*p[l[i].z])printf("TAK\n");
else printf("NIE\n");
}
}
return 0;
}