BZOJ3110 [Zjoi2013]K大数查询 线段树套线段树

yts1999 posted @ 2015年8月05日 16:31 in 树套树 with tags bzoj 树套树 线段树 , 589 阅读

第一位权值,第二位区间

太神了。。。

顺便学习了一下C++的指针的引用的用法

/**************************************************************
    Problem: 3110
    User: yts1999
    Language: C++
    Result: Accepted
    Time:18040 ms
    Memory:429864 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
 
struct Treenode {
    Treenode *lc,*rc;
    int sum,tag;
    Treenode() {
        lc = rc = NULL;
        sum = tag = 0;
    }
};
 
Treenode *root[200010];
int n,sz;
 
void lazylabel(Treenode *k,int l,int r) {
    if (! k->tag || l == r)
        return;
    if (k->lc == NULL)
        k->lc = new Treenode;
    if (k->rc == NULL)
        k->rc = new Treenode;
    k->lc->tag += k->tag;
    k->rc->tag += k->tag;
    int mid = (l + r) / 2;
    k->lc->sum += (mid - l + 1) * k->tag;
    k->rc->sum += (r - mid) * k->tag;
    k->tag = 0;
}
 
void modify(Treenode *&k,int l,int r,int a,int b) {
    if (k == NULL)
        k = new Treenode;
    lazylabel(k,l,r);
    if (l == a && r == b) {
        k->sum += r - l + 1;
        k->tag++;
        return;
    }
    int mid = (l + r) / 2;
    if (a <= mid)
        modify(k->lc,l,mid,a,min(mid,b));
    if (b > mid)
        modify(k->rc,mid + 1,r,max(mid + 1,a),b);
    k->sum = 0;
    if (k->lc != NULL)
        k->sum += k->lc->sum;
    if (k->rc != NULL)
        k->sum += k->rc->sum;
}
 
int query(Treenode *k,int l,int r,int a,int b) {
    if (k == NULL)
        return 0;
    lazylabel(k,l,r);
    if (l == a && r == b)
        return k->sum;
    int mid = (l + r) / 2;
    if (b <= mid)
        return query(k->lc,l,mid,a,b);
    else
        if (a > mid)
            return query(k->rc,mid + 1,r,a,b);
        else
            return query(k->lc,l,mid,a,mid) + query(k->rc,mid + 1,r,mid + 1,b);
}
 
void insert(int x,int y,int val) {
    int k = 1;
    for (int l = 1,r = n; l != r;) {
        int mid = (l + r) / 2;
        modify(root[k],1,n,x,y);
        if (val <= mid) {
            r = mid;
            k *= 2;
        }
        else {
            l = mid + 1;
            k = k * 2 + 1;
        }
    }
    modify(root[k],1,n,x,y);
}
 
int solve(int x,int y,int val) {
    int k = 1,l = 1;
    for (int r = n; l != r;) {
        int mid = (l + r) / 2;
        int t = query(root[k * 2],1,n,x,y);
        if (t >= val) {
            r = mid;
            k *= 2;
        }
        else {
            l = mid + 1;
            k = k * 2 + 1;
            val -= t;
        }
    }
    return l;
}
 
int main() {
    int m;
    scanf("%d%d",&n,&m);
    for (; m--;) {
        int op,x,y,z;
        scanf("%d%d%d%d",&op,&x,&y,&z);
        if (op == 1)
            insert(x,y,n - z + 1);
        else
            printf("%d\n",n - solve(x,y,z) + 1);
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter