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
|
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define mp make_pair
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define lowbit(x) ((x)&(-(x)))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif
const int inf=0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> pairs;
template<typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template<typename T,typename U>
inline void read(T &x,U &y){read(x);read(y);}
template<typename T,typename U,typename V>
inline void read(T &x,U &y,V &z){read(x);read(y);read(z);}
const int maxn=111111,maxvalue=10000000;
int n,m;
struct node
{
node *l,*r;
int value;
LL sum;
node():l(0),r(0),value(0),sum(0){}
node(node *ll,node *rr):l(ll),r(rr),value((ll?ll->value:0)+(rr?rr->value:0)),sum((ll?ll->sum:0)+(rr?rr->sum:0)){}
node(int vv,LL ss):l(0),r(0),value(vv),sum(ss){}
};
node *root[maxn];
char memorypool[maxn*sizeof(node)*60];//1 char=1 byte
char *memorypoolptr=memorypool;
inline void* myalloc(size_t size)
{
return (memorypoolptr+=size)-size;
}
#define newnode new (myalloc(sizeof(node))) node
node* insert(node *x,int k,int L=0,int R=maxvalue)
{
if (L==R) return newnode(x?x->value+1:1,x?((LL)(x->value+1)*k):k);
int mid=(L+R)>>1;
if (k<=mid) return newnode(insert(x?x->l:0,k,L,mid),x?x->r:0);
else return newnode(x?x->l:0,insert(x?x->r:0,k,mid+1,R));
}
node* erase(node *x,int k,int L=0,int R=maxvalue)
{
if (L==R) return newnode(x->value-1,(LL)(x->value-1)*k);
int mid=(L+R)>>1;
if (k<=mid) return newnode(erase(x?x->l:0,k,L,mid),x?x->r:0);
else return newnode(x?x->l:0,erase(x?x->r:0,k,mid+1,R));
}
LL sum(node *x,int k,int L=0,int R=maxvalue)
{
if (!x) return 0;
if (L==R) return (LL)k*L;
int mid=(L+R)>>1;
if (k<=(x->l?x->l->value:0)) return sum(x->l,k,L,mid);
else return sum(x->r,k-(x->l?x->l->value:0),mid+1,R)+((x->l)?x->l->sum:0);
}
pairs start[maxn],endd[maxn];
int cnts,cnte;
int main()
{
read(m,n);
int s,e,p;
rep(i,1,m)
{
read(s,e,p);
start[++cnts]=mp(s,p);
endd[++cnte]=mp(e+1,p);
}
sort(start+1,start+m+1);
sort(endd+1,endd+m+1);
root[0]=newnode();
int nows=1,nowe=1;
rep(i,1,n)
{
root[i]=root[i-1];
for (;start[nows].first==i;nows++) root[i]=insert(root[i],start[nows].second);
for (;endd[nowe].first==i;nowe++) root[i]=erase(root[i],endd[nowe].second);
}
int x,a,b,c,k;
LL pre=1;
rep(i,1,n)
{
read(x,a);read(b,c);
k=1+((a*pre+b)%c);
int tot=root[x]->value;
if (k>=tot) printf("%lld\n",pre=root[x]->sum);
else printf("%lld\n",pre=sum(root[x],k));
}
return 0;
}
|