洛谷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次操作。

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

我们分情况考虑：

若设大于等于s的数为cnt个

1、cnt >= c 我们直接选这c个就好了

2、cnt < c 这样不够选，那么我们考虑先选这cnt个大于等于s的数。那么要用其他的数来补上剩余的(c - cnt) * s。所以至少要求小于s的数的和是要大于(c - cnt) * s的。那么是不是满足小于s的数的和大于(c - cnt) * s的数列就一定满足条件呢？答案是肯定的。(可以感性理解2333)设想如果用贪心策略每一次都取出c个最大的数做减法的话我们一定可以平均把(c - cnt) * s分摊到每一个小于s的数上。

#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int maxn = 1e6 + 5;
int n, m, a, b, num[maxn], N = 1e9 + 5;
char s[2];

namespace SGT {
    struct node {int ch[2], sf[2];}tree[maxn * 10];
    int cnt, root;
    void push_up(int rt) {
        tree[rt].sf[0] = tree[tree[rt].ch[0]].sf[0] + tree[tree[rt].ch[1]].sf[0];
        tree[rt].sf[1] = tree[tree[rt].ch[0]].sf[1] + tree[tree[rt].ch[1]].sf[1];
    }
    void insert(int p, int tl, int tr, int dt, int & rt) {
        if(!rt) rt = ++cnt;
        if(tl == tr) {
            tree[rt].sf[0] += p * dt;
            tree[rt].sf[1] += dt; 
            return;
        }
        int mid = tl + tr >> 1;
        if(p <= mid) insert(p, tl, mid, dt, tree[rt].ch[0]);
        else insert(p, mid + 1, tr, dt, tree[rt].ch[1]);
        push_up(rt);
    }
    int query(int l, int r, int id, int tl, int tr, int rt) {
        if(!rt) return 0;
        if(tl == l && tr == r) return tree[rt].sf[id];
        int mid = tl + tr >> 1;
        if(r <= mid) return query(l, r, id, tl, mid, tree[rt].ch[0]);
        else if(mid < l) return query(l, r, id, mid + 1, tr, tree[rt].ch[1]);
        else {
            return query(l, mid, id, tl, mid, tree[rt].ch[0]) + 
                    query(mid + 1, r, id, mid + 1, tr, tree[rt].ch[1]);
        }
    }
}

int sum, cnt;
signed main() {
    scanf("%d%d", &n, &m);
    for(register int i = 1; i <= m; ++i) {
        scanf("%s%d%d", s, &a, &b);
        if(s[0] == 'U') {
            if(num[a]) SGT::insert(num[a], 1, N, -1, SGT::root);
            if(b) SGT::insert(b, 1, N, 1, SGT::root);
            num[a] = b;
        } else {
            sum = SGT::query(1, b - 1, 0, 1, N, SGT::root);
            cnt = SGT::query(b, N, 1, 1, N, SGT::root);
            printf("%s\n", sum >= (a - cnt) * b ? "TAK" : "NIE");
        }
    }
    return 0;
}

Rockdu's Blog