Brief description:

给定一个长度为 M 的环，每个位置属于 N 个国家之一。
有 K 个事件依次进行。每个事件形如 l, r, d 。
表示环上的一段连续区间中，每个位置的数 +d 。。。
国家 i 希望自己所属区域的数的和 >= Pi。。
返回每个国家达到各自需求的时间。如果达不到输出 NIE。

Analysis:

cdq 分治。）

void cdq(const VI I, int l, int r)
// 表示确定 I 中的事件，哪些处在 [l, r) 的左半区间，哪些处在右半区间、递归处理。
// 先生效所有属于左半边的操作，此时可以判断每个事件的归属。。
// 之后需要先递归右半边，把操作复原后递归左半边、、否则需要用一个额外的容器记录增量。

。。。对时间二分。。整体处理询问。。

//}/* .................................................................................................................................. */

const int N = int(3e5) + 9;

VI L[N]; LL A[N]; int ans[N];
int n, m, k;

namespace BIT{
    typedef LL intt;
    intt C[N];

    void Add(int x, int d){
        for (;x<=n;x+=low_bit(x)) C[x] += d;
    }
    intt Sum(int x){
        intt z = 0; for (;x;x^=low_bit(x)) z += C[x];
        return z;
    }
    void Add(int l, int r, int d){
        Add(l, d); Add(r+1, -d);
    }
    void Init(){
        //fill(C+1, C+n+1, 0);
    }
} //using namespace BIT;


struct Op{
    int l, r, d;
    void in(){
        RD(l, r, d);
    }
    void Add(){
        if (l <= r) BIT::Add(l, r, d);
        else BIT::Add(l, n, d), BIT::Add(1, r, d);
    }
    void Del(){
        if (l <= r) BIT::Add(l, r, -d);
        else BIT::Add(l, n, -d), BIT::Add(1, r, -d);
    }

} op[N];


void cdq(const VI I, int l, int r){

    if (I.empty()) return;

    if (l + 1 == r){
        ECH(i, I) ans[*i] = l;
    }
    else{
        int m = l + r >> 1;
        FOR(i, l, m) op[i].Add();

        VI Il, Ir; ECH(i, I){

            LL a = 0; ECH(ii, L[*i]){
                a += BIT::Sum(*ii);
                if (a >= A[*i]) break;
            }

            if (a < A[*i]){
                Ir.PB(*i);
            }
            else{
                Il.PB(*i);
            }
        }

        cdq(Ir, m, r); FOR(i, l, m) op[i].Del();
        cdq(Il, l, m);
    }
}


int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(m, n); REP_1(i, n) L[RD()-1].PB(i);
    VI I; REP(i, m) RD(A[i]), I.PB(i);
    RD(k); REP(i, k) op[i].in();

    cdq(I, 0, k+1);

    REP(i, m){
        if (ans[i] == k) puts("NIE");
        else OT(ans[i]+1);
    }
}

http://www.lydsy.com/JudgeOnline/problem.php?id=2527
http://main.edu.pl/en/archive/oi/18/met

References:

http://www.cnblogs.com/zig-zag/archive/2013/04/29/3051212.html

Posted by xiaodao
Category: BZOJ
Tags: cdq 分治