BZOJ2527

整体二分模板题

整体二分: 主要用于解决第K大问题

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstring>

#include<string>

#include<climits>

using namespace std;

inline int read()

{

    int x = 0, flag = 1;

    char c;

    while(! isgraph(c = getchar()))

        if(c == '-')

            flag *= - 1;

    while(isgraph(c))

        x = x * 10 + c - '0', c = getchar();

    return x * flag;

}

void println()

{

    putchar('N'), putchar('I'), putchar('E'), putchar('\n');

}

void println(int x)

{

    if(x < 0)

        putchar('-'), x *= - 1;

    if(x == 0)

        putchar('0');

    int ans[1 << 4], top = 0;

    while(x)

        ans[top ++] = x % 10, x /= 10;

    for(; top; top --)

        putchar(ans[top - 1] + '0');

    putchar('\n');

}

const int MAXN = 1 << 19, MAXM = 1 << 19, MAXK = 1 << 19;

int n, m;

vector<int> a[MAXN];

int p[MAXN];

int ID[MAXN];

struct rain

{

    int L, R, delta;

    rain(){}

    rain(int L, int R, int delta): L(L), R(R), delta(delta){}

}opt[MAXK << 1];

const int oo = INT_MAX;

int T;

long long tree[MAXM];

void add(int u, int delta)

{

    for(int i = u; i <= m; i += (i & (- i)))

        tree[i] += (long long)delta;

}

void modify(int u, int flag)

{

    if(opt[u].L <= opt[u].R)

        add(opt[u].L, flag * opt[u].delta), add(opt[u].R + 1, - flag * opt[u].delta);

    else

    {

        add(1, flag * opt[u].delta), add(opt[u].R + 1, - flag * opt[u].delta);

        add(opt[u].L, flag * opt[u].delta);

    }

}

long long query(int u)

{

    long long ret = 0;

    for(int i = u; i; i -= (i & (- i)))

        ret += tree[i];

    return ret;

}

int tmp[MAXN], mark[MAXN], ans[MAXN];

void solve(int L, int R, int optL, int optR)

{

    if(optL >= optR)

    {

        for(int i = L; i <= R; i ++)

            ans[ID[i]] = optL;

        return;

    }

    int mid = (optL + optR) >> 1;

    while(T < mid)

        modify(++ T, 1);

    while(T > mid)

        modify(T --, - 1);

    int cnt = 0;

    for(int i = L; i <= R; i ++)

    {

        long long sum = 0, now = ID[i];

        for(int j = 0; j < a[now].size(); j ++)

        {

            sum += query(a[now][j]);

            if(sum >= p[now])

                break;

        }

        if(sum >= p[now])

            mark[now] = 1, cnt ++;

        else

            mark[now] = 0;

    }

    int L1 = L, L2 = L + cnt;

    for(int i = L; i <= R; i ++)

        if(mark[ID[i]])

             tmp[L1 ++] = ID[i];

        else

            tmp[L2 ++] = ID[i];

    for(int i = L; i <= R; i ++)

        ID[i] = tmp[i];

    solve(L, L1 - 1, optL, mid);

    solve(L1, L2 - 1, mid + 1, optR);

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("BZOJ2527.in", "r", stdin);

    freopen("BZOJ2527.out", "w", stdout);

    #endif

    n = read(), m = read();

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

        a[read()].push_back(i);

    for(int i = 1; i <= n; i ++)

        p[i] = read();

    int k = read();

    int cnt;

    for(int i = 1; i <= k; i ++)

    {

        int L = read(), R = read(), delta = read();

        opt[i] = rain(L, R, delta);

    }

    opt[k + 1] = rain(1, m, oo);

    int T = 0;

    memset(tree, 0, sizeof(tree));

    for(int i = 1; i <= n; i ++)

        ID[i] = i;

    solve(1, n, 1, k + 1);

    for(int i = 1; i <= n; i ++)

    {

        if(ans[i] > k)

            println();

        else

            println(ans[i]);

    }

}