幸好有先见之明开了小号。。。
思路不难，利用差分思想在主席树上搞。如果省选遇到这种码力题岂不是要亡？？upd:原来我省选切掉带修主席树是因为这一口毒奶
吐槽：伪老年选手不会用win10。。。在竞赛室过不了样例的代码回家用XP过了。。。。岂不是跟不上时代？？
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<set> #include<map> using namespace std; typedef long long LL; struct node { int tim,p;LL d; }a[210000];int len; bool cmp(node n1,node n2){return n1.tim<n2.tim;} void ins(int tim,int p,LL d) { len++; a[len].tim=tim;a[len].p=p;a[len].d=d; } struct chairman_tree { int lc,rc,c;LL d; }tr[4100000];int trlen,rt[210000]; int maketree(int now,int l,int r,int p,int c,LL d) { if(now==0) { now=++trlen; tr[now].lc=tr[now].rc=0; tr[now].c=0;tr[now].d=0; } tr[now].c+=c;tr[now].d+=d; if(l==r)return now; else { int mid=(l+r)/2; if(p<=mid)tr[now].lc=maketree(tr[now].lc,l,mid,p,c,d); else tr[now].rc=maketree(tr[now].rc,mid+1,r,p,c,d); return now; } } int merge(int x,int y) { if(x==0||y==0)return x+y; tr[x].c+=tr[y].c; tr[x].d+=tr[y].d; tr[x].lc=merge(tr[x].lc,tr[y].lc); tr[x].rc=merge(tr[x].rc,tr[y].rc); return x; } int b[110000],blen; LL getk(int x,int l,int r,int k) { if(tr[x].c<k)return tr[x].d; if(l==r)return k*b[l]; int mid=(l+r)/2; if(tr[tr[x].lc].c>=k) return getk(tr[x].lc,l,mid,k); else return getk(tr[x].rc,mid+1,r,k-tr[tr[x].lc].c)+tr[tr[x].lc].d; } int erfen(int k) { int l=1,r=blen,ret; while(l<=r) { int mid=(l+r)/2; if(b[mid]<=k) { l=mid+1; ret=mid; } else r=mid-1; } return ret; } map<int,int>mp; set<int>s; int main() { freopen("a.in","r",stdin); freopen("lj.out","w",stdout); int n,m=100000,Q; scanf("%d%d",&n,&Q);len=0;blen=0; for(int i=1;i<=n;i++) { int l,r,p; scanf("%d%d%d",&l,&r,&p); ins(l,p,1); if(r<Q)ins(r+1,p,-1); b[++blen]=p; } sort(b+1,b+blen+1); blen=unique(b+1,b+blen+1)-b-1; sort(a+1,a+len+1,cmp); trlen=0;memset(rt,0,sizeof(rt)); int tp=0; for(int i=1,next;i<=len;i=next) { tp++; mp[a[i].tim]=tp;s.insert(a[i].tim); for(int j=i;j<=len;j++) { if(a[i].tim!=a[j].tim){next=j;break;} rt[tp]=maketree(rt[tp],1,m,erfen(a[j].p),a[j].d,LL(a[j].d*a[j].p)); if(j==len)next=len+1; } rt[tp]=merge(rt[tp],rt[tp-1]); } LL Pre=1; while(Q--) { int x,A,B,C,k; scanf("%d%d%d%d",&x,&A,&B,&C); k=1+(A*Pre+B)%C; if(x<*s.begin())Pre=0; else { if(mp[x]==0)x=*--s.lower_bound(x); Pre=getk(rt[mp[x]],1,m,k); } printf("%lld ",Pre); } return 0; }