[ZJOI 2013] bzoj3110 K大数查询 【树套树】

#include <cstdio>  
#include <vector>  
#include <algorithm>  
using namespace std;  
const int maxn = 50000 + 10;  
  
struct opt {  
    int i,k,c;  
    bool operator < (const opt& rhs) const {  
        if(c == rhs.c) return i < rhs.i;  
        return c > rhs.c;  
    }  
}A[maxn];  
  
vector<opt> T;  
int ID[maxn];  
bool ins[maxn];  
  
int main()  
{  
    int n,m;  
    scanf("%d %d",&n,&m);  
    for(int i = 1; i <= m; i++) {  
        int k,c;  
        scanf("%d %d %d %d",&k,&a,&b,&c);  
        A[i] = (opt){i,c};  
        if(k == 1) T.push_back(A[i]);  
    }  
    sort(T.begin(),T.end());  
    for(int i = 0; i < T.size(); i++) ID[T[i].i] = i;  
    for(int i = 1; i <= m; i++)  
        if(A[i].k == 1) ins[ID[i]] = 1;  
        else {  
            int j,c = 0;  
            for(j = 0; j < T.size(); j++) if(ins[j]) {  
                int len = min(A[i].b,T[j].b) - max(A[i].a,T[j].a) + 1;  
                if(len <= 0) continue;  
                if((c += len) >= A[i].c) break;  
            }  
            printf("%dn",T[j].c);  
        }  
    return 0;  
} 

    #include "cstdio"  
    #define lowbit(x) (x & (-x))   
       
    using namespace std;  
       
    const int Nmax = 50005;  
       
    int N,M;  
    struct Option{  
        int sign,y,c;  
    }op[Nmax];  
       
    int tot = -1,ans[Nmax];  
    int q[Nmax],tmp[2][Nmax];  
       
    namespace BIT{  
        int t[Nmax][2],d[Nmax][2];  
       
        void update(bool s,int pos,int c)  
        {  
            for (int i = pos; i <= N; i += lowbit(i)) {  
                if (t[i][s] != tot) { t[i][s] = tot; d[i][s] = 0; }  
                d[i][s] += c;  
            }  
        }  
           
        int get_sum(bool s,int pos)  
        {  
            int res = 0;  
            for (int i = pos; i; i -= lowbit(i)) {  
                if (t[i][s] != tot) { t[i][s] = tot; d[i][s] = 0; }  
                res += d[i][s];  
            }  
            return res;  
        }  
           
        void Add(int x,int y)  
        {  
            update(0,1); update(0,y + 1,-1);  
            update(1,x); update(1,-(y + 1));  
        }  
           
        int Query(int x,int y)  
        {  
            int temp = get_sum(0,y) * (y + 1) - get_sum(1,y);  
            temp -= get_sum(0,x - 1) * x - get_sum(1,x - 1);  
            return temp;  
        }  
    }  
       
    void solve(int L,int r)  
    {  
        if (L > R) return;  
           
        ++tot; int mid = (l + r) >> 1;  
        if (l == r) {  
            for (int i = L; i <= R; ++i) if (op[q[i]].sign == 2) ans[q[i]] = mid;  
            return;  
        }  
           
        tmp[0][0] = tmp[1][0] = 0; using namespace BIT;  
        for (int i = L; i <= R; ++i) {  
            int temp = q[i];  
            if (op[temp].sign == 1) {  
                if (op[temp].c <= mid) tmp[0][++tmp[0][0]] = temp;  
                else {  
                    tmp[1][++tmp[1][0]] = temp;  
                    Add(op[temp].x,op[temp].y);  
                }  
            } else {  
                int cnt = Query(op[temp].x,op[temp].y);  
                if (cnt < op[temp].c) {  
                    op[temp].c -= cnt;  
                    tmp[0][++tmp[0][0]] = temp;  
                } else tmp[1][++tmp[1][0]] = temp;  
            }  
        }  
           
        int tl = L,t2 = L + tmp[0][0] - 1;  
        for (int i = 1; i <= tmp[0][0]; ++i) q[tl++] = tmp[0][i];  
        for (int i = 1; i <= tmp[1][0]; ++i) q[tl++] = tmp[1][i];  
        solve(L,t2,mid); solve(t2 + 1,r);  
    }  
       
    int main()  
    {  
        scanf("%d%d",&N,&M);  
        for (int i = 1; i <= M; ++i) {  
            scanf("%d%d%d%d",&op[i].sign,&op[i].x,&op[i].y,&op[i].c);  
            q[i] = i;  
        }  
        solve(1,M,N);  
        for (int i = 1; i <= M; ++i) {  
            if (op[i].sign == 2) printf("%dn",ans[i]);  
        }  
           
        return 0;  
    }  

（编辑：青岛站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!