【ZJOI2013amp;amp;BZOJ3110】K大数查询

Description

有n 个位置和m 个操作。操作有两种，每次操作如果是1 a b c 的形式，表示往第a 个位置到第b 个位置每个位置加入一个数c。如果操作形如2 a b c 的形式，表示询问从第a 个位置到第b 个位置，第c 大的数是多少。

Solution

树套树的模板题

找矩阵中第k大的数，肯定是用权值线段树维护区间线段树啦！
在JZOJ跑的正常，BZOJ上怎么都过不了TAT。常数不好啊！毕竟是第一次打树套树。

只能之后打CDQ分治的时候去打打了

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
int i,j,k,l,n,m,ans,root[20000005];
int a,b,c,d,num;
struct node{
    int l,r,sum,add;
}t[20000005];
void down(int x,int l,int r){
    if(l==r)return;
    int mid=(l+r)/2;
    if(t[x].add){
        if(!t[x].l)t[x].l=++num;
        if(!t[x].r)t[x].r=++num;
        t[t[x].l].add+=t[x].add,t[t[x].r].add+=t[x].add;
        t[t[x].l].sum+=(mid-l+1)*t[x].add,t[t[x].r].sum+=(r-mid)*t[x].add;
        t[x].add=0;
    }
}
void change(int &x,int r,int y,int z){
    if(!x)x=++num;
    down(x,r);
    if(l==y&&r==z){
        t[x].sum+=r-l+1;t[x].add++;
        return;
    }
    int mid=(l+r)/2;
    if(z<=mid)change(t[x].l,mid,y,z);
    else if(y>mid)change(t[x].r,mid+1,z);
    else{
        change(t[x].l,mid);
        change(t[x].r,z);
    }
    t[x].sum=t[t[x].l].sum+t[t[x].r].sum;
}
void insert(int x,int z){
    int l=1,r=n,o=1;
    while(l<r){
        int mid=(l+r)/2;
        change(root[o],1,z);
        if(x<=mid)r=mid,o*=2;else l=mid+1,o=o*2+1;
    }
    change(root[o],z);
}
int find(int x,int z){
    if(!x)return 0;
    down(x,r);
    if(l==y&&r==z){
        return t[x].sum;
    }
    int mid=(l+r)/2;
    if(z<=mid)return find(t[x].l,z);
    else if(y>mid)return find(t[x].r,z);
    else{
        return find(t[x].l,mid)+find(t[x].r,z);
    }
}
int solve(int x,o=1;
    while(l<r){
        int mid=(l+r)/2;
        int u=find(root[o*2],z);
        if(u>=x)r=mid,o=o*2+1,x-=u;
    }
    return n-l+1;
}
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main(){
    n=read();m=read();
    fo(i,m){
        a=read();b=read();c=read();d=read();
        if(a==1){
            d=n-d+1;
            insert(d,c);
        }
        else{
            printf("%dn",solve(d,c));
        }
    }
}

（编辑：晋中站长网）

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