POI2011 Meteors

整体二分板子题。

自己还能YY点东西…

大概就是递归下去二分。

每次对于一个二分区间$[left,right]$，设中点为$mid$，那么把在$[left,mid]$范围内满足条件的询问扔到一起，把满足不了条件的询问也扔到一起，然后分别塞给$[left,mid]$区间和$[mid+1,right]$区间。

然后递归下去即可。

对于这题复杂度很显然是$O(n\log ^2 )$。

考虑二分的每一层都有$O(n)$个询问要处理，这些询问全部check一遍（使用树状数组）的复杂度是$O(n\log  n)$的。

#include <assert.h>
#include <iostream>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 3e5 + 10;
int_t barr[LARGE + 1];
int n, m, k;

struct Opt {
    int left, right, val;
} opts[LARGE + 1];
std::vector<int> stations[LARGE + 1];
//某个国家的期望值
int req[LARGE + 1];
//整体二分使用的数组
int arr[LARGE + 1];
int result[LARGE + 1];
int lowbit(int x) { return x & -x; }
int_t query(int x) {
    int_t result = 0;
    while (x >= 1) {
        result += barr[x];
        x -= lowbit(x);
    }
    return result;
}
void addPos(int x, int val) {
    while (x <= m) {
        barr[x] += val;
        x += lowbit(x);
    }
}
void add(int left, int right, int val) {
    addPos(left, val);
    addPos(right + 1, -val);
}
//执行操作区间
void execute(int left, int right, int arg = 1) {
    for (int i = left; i <= right; i++) {
        const auto& curr = opts[i];
        if (curr.left <= curr.right)
            add(curr.left, curr.right, curr.val * arg);
        else {
            add(curr.left, m, curr.val * arg);
            add(1, curr.right, curr.val * arg);
        }
    }
}
//[left,right] 当前二分的答案区间
//[cleft,cright] 当前二分的答案区间对应的询问
void process(int left, int right, int offset, int* cleft, int* cright) {
    //没有询问，没必要递归
    if (cleft > cright) return;
    int mid = (left + right) / 2;
    //应用mid及之前的操作
    execute(offset, mid, 1);
    static int oks[LARGE + 1], notOks[LARGE + 1];
    oks[0] = notOks[0] = 0;
    for (auto ptr = cleft; ptr <= cright; ptr++) {
        __int128_t count = 0;
        for (auto x : stations[*ptr]) count += query(x);
        if (count >= req[*ptr])
            oks[++oks[0]] = *ptr;
        else
            notOks[++notOks[0]] = *ptr;
    }
    auto ptr = cleft;
    for (int i = 1; i <= oks[0]; i++) *(ptr++) = oks[i];
    auto midptr = ptr - 1;
    for (int i = 1; i <= notOks[0]; i++) *(ptr++) = notOks[i];
    assert(ptr == cright + 1);
    // //递归终点，统计答案
    if (left == right) {
        //没有撤销！！
        execute(offset, mid, -1);
        for (int i = 1; i <= oks[0]; i++) result[oks[i]] = left;
        for (auto i = 1; i <= notOks[0]; i++) result[notOks[i]] = -1;
        return;
    }
    assert(offset == left);
    process(mid + 1, right, mid + 1, midptr + 1, cright);
    execute(offset, mid, -1);
    process(left, mid, offset, cleft, midptr);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x;
        scanf("%d", &x);
        stations[x].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        arr[i] = i;
        scanf("%d", &req[i]);
    }
    scanf("%d", &k);
    for (int i = 1; i <= k; i++) {
        auto& curr = opts[i];
        scanf("%d%d%d", &curr.left, &curr.right, &curr.val);
    }
    process(1, k, 1, &arr[1], &arr[n]);
    for (int i = 1; i <= n; i++) {
        if (result[i] != -1) {
            printf("%d\n", result[i]);
        } else {
            printf("NIE\n");
        }
    }
    return 0;
}