CQOI2015任务查询系统

题目链接

主席树。

把区间的影响挂在左端点与右端点，建树时顺便对应的插入与删除。

维护一段值域区间的和与数字个数，查询时要注意与第k大的数相同的数可能有很多。

复杂度O(nlogn)

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<vector>

#include<algorithm>

#include<queue>

#include<cmath>

#include<stack>

#include<map>

#define P puts("lala")

#define cp cerr<<"lala"<<endl

#define ln putchar('\n')

#define sp putchar(' ')

#define pb push_back

#define pf push_front

#define fi first

#define se second

#define mkp make_pair

using namespace std;

typedef pair<int,int> pii;

inline void read(int &re)

{

    char ch=getchar();int g=1;

    while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();}

    re=0;

    while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar();

    re*=g;

}

typedef long long ll;

inline void read(ll &re)

{

    char ch=getchar();ll g=1;

    while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();}

    re=0;

    while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+ch-48ll,ch=getchar();

    re*=g;

}

const int N=100050;

int p[N],b[N],to[N],n,m,L[N],R[N],tot,rt[N],ch[N*45][2],cnt[N*45],sz;

ll sum[N*45];

vector<int>ve1[N],ve2[N];

void build(int &o,int l,int r)

{

    o=++sz;

    sum[o]=cnt[o]=0;

    if(l==r) return ;

    int mid=l+r>>1;

    build(ch[o][0],l,mid);build(ch[o][1],mid+1,r);

}

void update(int &o,int last,int l,int r,int x,int k) //k*x

{

    if(o==last)

    {

        o=++sz;

        ch[o][0]=ch[last][0];ch[o][1]=ch[last][1];

        cnt[o]=cnt[last]+k;sum[o]=sum[last]+k*b[x];

    }

    else

    {

        cnt[o]+=k;sum[o]+=k*b[x];

    }

    if(l==r) return ;

    int mid=l+r>>1;

    if(x<=mid) update(ch[o][0],ch[last][0],l,mid,x,k);

    else update(ch[o][1],ch[last][1],mid+1,r,x,k);

}

ll query(int o,int l,int r,int k)

{

    if(l==r) {return b[l]*k;}

    int mid=l+r>>1;

    ll ans=0;

    if(k<=cnt[ch[o][0]]) return query(ch[o][0],l,mid,k);

    else return query(ch[o][1],mid+1,r,k-cnt[ch[o][0]])+sum[ch[o][0]];

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("1.in","r",stdin);freopen("1.out","w",stdout);

#endif

    int i,j,opt,T;

    read(m);read(n);

    for(i=1;i<=m;++i)

    {

        read(L[i]);read(R[i]);read(p[i]);b[i]=p[i];

    }

    sort(b+1,b+1+m);

    tot=unique(b+1,b+1+m)-(b+1);

    for(i=1;i<=m;++i) to[i]=lower_bound(b+1,b+1+tot,p[i])-b;

    build(rt[0],1,tot);

    for(i=1;i<=m;++i) ve1[L[i]].pb(to[i]),ve2[R[i]+1].pb(to[i]);

    for(i=1;i<=n;++i)

    {

        int siz=ve1[i].size();

        rt[i]=rt[i-1];

        for(j=0;j<siz;++j) update(rt[i],rt[i-1],1,tot,ve1[i][j],1);

        siz=ve2[i].size();

        for(j=0;j<siz;++j) update(rt[i],rt[i-1],1,tot,ve2[i][j],-1);

    }

    ll pre=1;

    for(int cas=1;cas<=n;++cas)

    {

        int x,a,b,c,k;

        read(x);read(a);read(b);read(c);

        k=1+(a*pre+b)%c;

        if(k>cnt[rt[x]]) k=cnt[rt[x]];

        pre=query(rt[x],1,tot,k);

        printf("%lld\n",pre);

    }

    return 0;

}

/*

*/

CQOI2015任务查询系统的相关教程结束。