碼迷,www.tparu.icu
吉利平特名人堂 > 其他好文 > 詳細

平特心水:P3332 [ZJOI2013]K大數查詢 整體二分

時間:2019-05-23 18:16:39      閱讀:24      評論:0      收藏:0      [點我收藏+]

吉利平特名人堂 www.tparu.icu 標簽:sum   流程   隊列   沒有   define   odi   pre   void   ring   

終于入門整體二分了,勉勉強強算是搞懂了一個題目吧。

整體二分很多時候可以比較好的離線處理區間\(K\)大值的相關問題??悸撬惴鞒蹋?/p>

操作隊列\(arr\),其中有詢問和修改兩類操作。

每次在答案的可行值域上二分一個\(mid\),把詢問的答案\(>mid\)的分在\(R\)部,\(<=mid\)的分在\(L\)部。把修改的值\(>mid\)的分在\(R\)部,\(<=mid\)的分在\(L\)部。

何謂整體二分?就是直接一起二分所有的詢問操作的答案,然后暴力掃描當前操作區間,將其劃分為答案的左子區間與右子區間兩個部分。

那么以什么為劃分依據呢?看看這個操作對于左子區間有沒有貢獻。如果沒有,那么就劃分到右子區間中,然后將這個操作的權值更改為這個貢獻減去所需的貢獻,反之,則劃分到左子區間中,同時將這個操作的貢獻加入某一個容器,為詢問操作服務。

這么說可能有點暈。就這道題說的話,應該是這樣:

我們設尚未解決的操作區間為\([ql,qr]\),答案區間為[l,r][l,r],令當前答案為\(mid\)。

則若該操作是添加操作,如果其添加的\(C<=mid\),這此次操作對于左子區間有貢獻,加入左子區間中,并將區間線段樹中的區間\([q[i].l,q[i].r]\)整體加\(1\).

反之,則將操作加入到右子區間中。

若該操作是詢問操作,如果當前的\(mid\)在線段樹中查詢到的,比它大的數的個數\(query()>=q[i].k\),則證明該詢問操作應該在右子區間內可以找到答案。反之,則將\(q[i].k-=query()\),減去此次查詢的貢獻,然后將詢問操作添加到左子區間中。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define int long long
const int N = 50000 + 5;

struct Ask {
    int l, r, v, id, op;
    
    void read () {
        cin >> op >> l >> r >> v; 
    } 
    
}q[N], tl[N], tr[N];

int ans[N], tag[N << 2], clr[N << 2], sum[N << 2];

int n, m, Q;

#define lc (p << 1)
#define rc (p << 1 | 1)
#define mid ((l + r) >> 1)

void pushdown (int p, int l, int r) {
    if (clr[p]) {
        clr[p] = 0;
        tag[lc] = tag[rc] = 0;
        sum[lc] = sum[rc] = 0;
        clr[lc] = 1, clr[rc] = 1;
    }
    if (tag[p]) {
        tag[lc] += tag[p];
        tag[rc] += tag[p];
        sum[lc] += tag[p] * (mid - l + 1);
        sum[rc] += tag[p] * (r - mid);
        tag[p] = 0;
    }
}   
 
void push_up (int p) {
    sum[p] = sum[lc] + sum[rc];
} 
 
void modify (int ql, int qr, int w, int p = 1, int l = 1, int r = n) {
    if (ql <= l && r <= qr){
        tag[p] += w;
        sum[p] += w * (r - l + 1);
        return;
    }
    pushdown (p, l, r);
    if (ql <= mid) modify (ql, qr, w, lc, l, mid);
    if (mid < qr) modify (ql, qr, w, rc, mid + 1, r);
    push_up (p);
}

int query (int ql, int qr, int p = 1, int l = 1, int r = n) {
    if (ql <= l && r <= qr) {
        return sum[p];
    }
    int ret = 0; pushdown(p,l,r);
    if (ql <= mid) ret += query (ql, qr, lc, l, mid);
    if (mid < qr) ret += query (ql, qr, rc, mid + 1, r);
    return ret;
}

void solve (int st, int en, int l, int r) {
    // [st, en] -> 處理操作的左右端點
    // [l, r] -> 對應值域 
    if (l == r) {
        for (int i = st; i <= en; ++i) {
            if (q[i].op == 2) ans[q[i].id] = l; // 查詢
        }
        return;  
    }
    int L = 0, R = 0;
    clr[1] = 1; tag[1] = sum[1] = 0;
    for (int i = st; i <= en; ++i) {
        if (q[i].op == 1){
            if (q[i].v > mid) { // > mid 的操作對于答案 <= mid 的詢問不會影響 
                modify (q[i].l, q[i].r, 1);
                tr[++R] = q[i];
            } else {
                tl[++L] = q[i];
            }
        } else {
            int val = query (q[i].l, q[i].r);
            if (val < q[i].v){
                q[i].v -= val;
                tl[++L] = q[i]; // L部答案 <= mid 
            }else{
                tr[++R] = q[i]; // R部答案 >  mid 
            }
        }
    }
    for (int i = 1; i <= L; ++i) {
        q[st + i - 1] = tl[i];
    }
    for (int i = L + 1; i <= L + R; ++i) {
        q[st + i - 1] = tr[i - L];
    }
    solve (st, st + L - 1, l, mid);
    solve (st + L, en, mid + 1, r);
}

signed main () {
    cin >> n >> m; 
    for (int i = 1; i <= m; ++i) { 
        q[i].read ();
        if (q[i].op == 2) {
            q[i].id = ++Q;
        }
    }
    solve (1, m, -n, n);
    for (int i = 1; i <= Q; ++i) {
        cout << ans[i] << endl;
    }
}

P3332 [ZJOI2013]K大數查詢 整體二分

標簽:sum   流程   隊列   沒有   define   odi   pre   void   ring   

原文地址:https://www.cnblogs.com/maomao9173/p/10913560.html

(0)
(0)
   
舉報
評論 一句話評論(0
0條  
登錄后才能評論!
? 2014 吉利平特名人堂 版權所有 京ICP備13008772號-2
迷上了代碼!
11选5计划软件安卓 定位胆大小单双诀窍 牛牛看4张牌抢庄技巧 pk10赛车直播官网平台 买江西时时 七星彩技巧准确率99 求时时彩后一稳赚方法 福建时时分析软件 福利彩票快三投注稳赚技巧 看牌抢庄牛牛20元进场 江苏时时技巧集锦 极速赛车技巧分享 云鼎时时彩3878 双色球稳赚不赔的技术 3d组六3码遗漏分析 北京pk赛车手机版