BZOJ 3932: [CQOI2015]任務查詢系統 [主席樹]

題意

給出 n 個由三元組(si,ei,pi)表示的區間, si,ei 表示頭尾(包括頭尾), pi 表示這個區間的權重

給出 m 個詢問,詢問包含位置x的按權重排序前 k 小的區間的權重和

輸入先給出所有三元組,詢問強制線上

題解

主席樹的權值線段樹按照pi來搞,因為值域比較大,要離散一下

所有三元組先讀入,拆成兩個端點

每個端點維護兩個權值, sum1 表示權重和, sum2 表示區間個數

s 和e+1, s 上為正的,e+1上為負的,相當于差分

然後把每個端點按時間軸插入主席樹

注意下空間

#include<cstdio>
#include<algorithm>
#define N 100005
#define M N*40
#define LL long long
using namespace std;

int n,m,sz,ls[M],rs[M],P[N],pos[N],id[N],root[N];
LL tmp,sum1[M],sum2[M];
struct node{
    int tim,pos,v1,v2;
}a[N<<];

inline int read(){
    int a=;char f=,c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-;c=getchar();}
    while(c>='0'&&c<='9'){a=a*10+c-'0';c=getchar();}
    return a*f;
}

inline bool cmp(int x,int y){return P[x]<P[y];}

inline bool cmp1(node x,node y){return x.tim<y.tim;}

void insert(int &x,int l,int r,int lst,int p,int v1,int v2){
    x=++sz;
    ls[x]=ls[lst],rs[x]=rs[lst];
    sum1[x]=sum1[lst]+v1,sum2[x]=sum2[lst]+v2;
    if(l==r) return;
    int mid=l+r>>;
    if(p<=mid) insert(ls[x],l,mid,ls[lst],p,v1,v2);
    else insert(rs[x],mid+,r,rs[lst],p,v1,v2);
    return;
}

LL query(int x,int l,int r,int k){
    if(l==r) return sum1[x]+tmp;
    int mid=l+r>>,cnt=sum2[ls[x]];
    if(cnt>=k) return query(ls[x],l,mid,k);
    else{
        tmp+=sum1[ls[x]];
        return query(rs[x],mid+,r,k-cnt);
    }
}

int main(){
    freopen("testdata.in","r",stdin);
//  freopen("testdata.out","w",stdout);
    n=read(),m=read();
    int i,j;
    for(i=,sz=;i<=n;++i){
        int s=read(),t=read()+;P[i]=read();
        a[++sz].tim=s,a[sz].v1=P[i],a[sz].v2=;
        a[++sz].tim=t,a[sz].v1=-P[i],a[sz].v2=-;
        id[i]=i;
    }
    sort(id+,id+n+,cmp);
    for(i=;i<=n;++i) pos[id[i]]=i;
    for(i=,sz=;i<=n;++i) a[++sz].pos=pos[i],a[++sz].pos=pos[i];
    sort(a+,a+sz+,cmp1);
    sz=;
    for(i=,j=;i<=m;++i){
        root[i]=root[i-];
        while(a[j].tim==i){
            insert(root[i],,n,root[i],a[j].pos,a[j].v1,a[j].v2);
            ++j;
        }
    }
    LL ans=,A,B,C,K,x;
    while(m--){
        x=read(),A=read(),B=read(),C=read();
        K=+(A*ans+B)%C;
        tmp=;
        ans=query(root[x],,n,K);
        printf("%lld\n",ans);
    }
    return ;
}
           

為什麼我總是跑得這麼慢啊