BZOJ 2527. [Poi2011]Meteors

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