【BZOJ4378】【POI2015】Logistyka
对于每次询问c，s，首先统计出数列中大于等于s的元素个数cnt。如果cnt>=c那么显然满足条件；否则对剩下的n-cnt个小于s的数，如果他们的和大于等于s*(n-cnt)那么满足条件（请感性地去理解 ---- JD）。
用两个树状数组维护一下就好了。
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 | #include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;const int maxn=1000010;void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}char readchar() {char ch;while ((ch=getchar())!='U' && ch!='Z');return ch;}struct Info {int type,a,b;}I[maxn];int s[maxn],v[maxn],vcnt;LL f1[maxn],f2[maxn];int n,m;inline int lowbit(int x) {return x&-x;}void Change(LL *arr,int pos,LL c) {while (pos<=vcnt) arr[pos]+=c,pos+=lowbit(pos);}LL Query(LL *arr,int pos) {LL res=0;while (pos) res+=arr[pos],pos-=lowbit(pos);return res;}int main(){ read(n);read(m); for (int i=1;i<=m;i++) { char cot=readchar(); I[i].type=cot=='Z'; read(I[i].a),read(I[i].b); v[i]=I[i].b; } v[n+1]=0; sort(v+1,v+2+m);vcnt=unique(v+1,v+2+m)-(v+1); Change(f1,1,n); for (int i=1;i<=n;i++) s[i]=1; for (int i=1;i<=m;i++) if (I[i].type==0) I[i].b=lower_bound(v+1,v+1+vcnt,I[i].b)-v; for (int i=1;i<=m;i++) if (I[i].type==0) { int numu=s[I[i].a],numv=I[i].b; Change(f1,numu,-1),Change(f2,numu,-v[numu]); Change(f1,numv, 1),Change(f2,numv, v[numv]); s[I[i].a]=I[i].b; } else { int pos=lower_bound(v+1,v+1+vcnt,I[i].b)-v; int cnt=n-Query(f1,pos-1); LL prev=Query(f2,pos-1); if (cnt>=I[i].a || prev>=(LL)(I[i].a-cnt)*(I[i].b)) puts("TAK");else puts("NIE"); } return 0;} |
评论 (0)
