P3586 [POI2015]LOG

题目描述

维护一个长度为n的序列，一开始都是0，支持以下两种操作：1.U k a 将序列中第k个数修改为a。2.Z c s 在这个序列上，每次选出c个正数，并将它们都减去1，询问能否进行s次操作。每次询问独立，即每次询问不会对序列进行修改。

输入输出格式

输入格式：

第一行包含两个正整数n,m(1<=n,m<=1000000)，分别表示序列长度和操作次数。接下来m行为m个操作，其中1<=k,c<=n，0<=a<=10^9，1<=s<=10^9。

输出格式：

包含若干行，对于每个Z询问，若可行，输出TAK，否则输出NIE。

输入输出样例

输入样例#1：复制

输出样例#1：复制

NIE

TAK

NIE

TAK

说明

维护一个长度为n的序列，一开始都是0，支持以下两种操作：

1.U k a 将序列中第k个数修改为a。

2.Z c s 在这个序列上，每次选出c个正数，并将它们都减去1，询问能否进行s次操作。

每次询问独立，即每次询问不会对序列进行修改。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 1000010

using namespace std;

int a[maxn],x[maxn],y[maxn],z[maxn],num[maxn],hash[maxn];

int n,m,cnt;

struct node{

    long long c[maxn];

    void add(int x,int y){

        while(x<=cnt){

            c[x]+=y;

            x+=x&-x;

        }

    }

    long long query(int x){

        long long res=;

        while(x){

            res+=c[x];

            x-=x&-x;

        }

        return res;

    }

}bit1,bit2;

int main(){

    scanf("%d%d",&n,&m);

    char s[];

    for(int i=;i<=m;i++){

        scanf("%s",s);

        scanf("%d%d",&x[i],&y[i]);num[i]=y[i];

        if(s[]=='U')z[i]=;

        else z[i]=;

    }

    sort(num+,num+m+);

    hash[cnt=]=num[];

    for(int i=;i<=m;i++)

        if(num[i]!=num[i-])hash[++cnt]=num[i];

    for(int i=;i<=m;i++)y[i]=lower_bound(hash+,hash+cnt+,y[i])-hash;

    for(int i=;i<=m;i++){

        if(z[i]){

            if(a[x[i]]){

                int j=a[x[i]];

                bit1.add(j,-);bit2.add(j,-hash[j]);

            }

            a[x[i]]=y[i];

            bit1.add(y[i],);bit2.add(y[i],hash[y[i]]);

        }

        else {

            long long num1=bit2.query(y[i]-);

            long long num2=bit1.query(cnt);

            long long num3=bit1.query(y[i]-);

            if(num1>=1LL*(x[i]-num2+num3)*hash[y[i]])puts("TAK");

            else puts("NIE");

        }

    }

    return ;

}

巴特西

洛谷 P3586 [POI2015]LOG

P3586 [POI2015]LOG

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章