@OceanEye7年前
05/20
15:36
裸的主席树
前k个可能是一个优先级的一部分
看代码吧:-D
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define N 100010 struct rec { int id,pos,val; }RRR[N<<1]; int ____; bool comp(const rec &x,const rec &y) { return x.id<y.id; } int n,m,p; void pre() { read(n); read(m); int _,__,___; for(int i=1;i<=n;i++) { read(_); read(__); read(___); RRR[____].id=_; RRR[____].val=1; RRR[____].pos=___; ____++; RRR[____].id=__+1; RRR[____].val=-1; RRR[____].pos=___; ____++; } sort(RRR,RRR+____,comp); } struct node { int l,r,c[2],cnt; ll sum; }pool[N<<6]; #define L pool[x].l #define R pool[x].r #define Lc pool[x].c[0] #define Rc pool[x].c[1] #define SUM pool[x].sum #define CNT pool[x].cnt int RT[N],pcnt; void PushUP(int x) { SUM=pool[Lc].sum+pool[Rc].sum; CNT=pool[Lc].cnt+pool[Rc].cnt; } void insert(const int &pos,int& x,const int &val) { pool[++pcnt]=pool[x]; x=pcnt; if(L==R) { CNT+=val; SUM=1LL*CNT*pos; return; } int mid=(L+R)>>1; if(mid>=pos) { if(Lc==0)pool[Lc].l=L,pool[Lc].r=mid; insert(pos,Lc,val); } else { if(Rc==0)pool[Rc].l=mid+1,pool[Rc].r=R; insert(pos,Rc,val); } PushUP(x); } ll sum(int x,int k) { if(x==0) return 0; if(CNT<=k) return SUM; if(L==R) { return (ll)min(k,CNT)*L; } return pool[Lc].cnt>=k?sum(Lc,k):pool[Lc].sum+sum(Rc,k-pool[Lc].cnt); } int main() { freopen("BZOJ3932.in","r",stdin); pre(); ____=0; pool[0].l=1; pool[0].r=10000050; for(int i=1;i<=m;i++) { RT[i]=RT[i-1]; for(;RRR[____].id==i;____++) insert(RRR[____].pos,RT[i],RRR[____].val); } static int Q,T,A,B,C,k,mid; ll pre=1; while(m--) { read(T); read(A); read(B); read(C); pre%=C; A%=C; B%=C; k=1+(ll)(1LL*A*pre+B)%C; printf("%lld\n",pre=sum(RT[T],k)); } return 0; } |