[BZOJ 3932]CQOI 2015タスク照会システム|議長ツリー
6872 ワード
ゞ CQOI好良心,都是裸题.ゞ任務の差分を裸で議長の木に登ればいい.の
#include
#include
#include
#define ll long long
#define N 100005
#define M 4000010
using namespace std;
struct task{
int l,r,p;
}t[N];
struct node{
int del,p,next;
}ed[N*2];
int i,n,m,x,A,B,C,k,nd=0,cnt=0,ne=0,a[N],root[N],size[M],newq[N],lc[M],rc[M];
ll pre;
bool cmp(task a,task b){return a.pint s,int p,int d)
{
ed[++ne].del=d;ed[ne].p=p;
ed[ne].next=a[s];a[s]=ne;
}
int update(int last,int l,int r,int q,int del)
{
int x=++nd,mid=(l+r)>>1;
size[x]=size[last]+del;
lc[x]=rc[x]=0;
if (l==r) return x;
if (q<=mid) lc[x]=update(lc[last],l,mid,q,del),rc[x]=rc[last];
else lc[x]=lc[last],rc[x]=update(rc[last],mid+1,r,q,del);
return x;
}
ll query(int x,int l,int r,int k)
{
if (k>size[x]) k=size[x];
if (!x||k==0) return 0ll;
if (l==r) return (ll)k*newq[l];
int mid=(l+r)>>1;
if (size[lc[x]]>=k) return query(lc[x],l,mid,k);else return query(lc[x],l,mid,size[lc[x]])+query(rc[x],mid+1,r,k-size[lc[x]]);
}
int main()
{
freopen("task.in","r",stdin);
freopen("task.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) scanf("%d%d%d",&t[i].l,&t[i].r,&t[i].p);
for (i=1;i<=m;i++) a[i]=0;
sort(t+1,t+1+n,cmp);
t[0].p=-1;
for (i=1;i<=n;i++)
{
if (t[i].p!=t[i-1].p) cnt++,newq[cnt]=t[i].p;
add(t[i].l,cnt,1);if (t[i].r!=m) add(t[i].r+1,cnt,-1);
}
root[0]=0;
for (i=1;i<=m;i++)
{
root[i]=root[i-1];
for (int j=a[i];j;j=ed[j].next)
root[i]=update(root[i],1,cnt,ed[j].p,ed[j].del);
}
pre=1ll;size[0]=0;
for (i=1;i<=m;i++)
{
scanf("%d%d%d%d",&x,&A,&B,&C);
k=1+(A*pre+B)%C;
pre=query(root[x],1,cnt,k);
printf("%lld
",pre);
}
}