This paper introduces two methods of this question:

Method 1

Front cheese

1. Line segment tree : a very important data structure
2. Tree array : a very important data structure

Concrete realization

For interval modification, it is easy to think of tree array for single point query. As for the sum of k numbers before query, it can be lost to weight line segment tree. So the first obvious method is to set a line segment tree for tree array

Code

```#include<bits/stdc++.h>
#define REP(i,first,last) for(int i=first;i<=last;++i)
#define DOW(i,first,last) for(int i=first;i>=last;--i)
using namespace std;
const int maxN=5e5+7;
const int INF=2147483647;
int N,M;
int op[maxN];
int s[maxN],e[maxN],p[maxN];
int arr[maxN];
int sor[maxN];
int len=0;
map<int,int>Hash;//A lot of data needs to be discretized
int val__[maxN];//Record the original value represented by each number after discretization
struct Tree//Dynamic open point line segment tree
{
int sum,lson,rson;
long long sum_;
}tree[maxN*32];
int point_cnt=0;
//Line tree standard define
#define LSON tree[now].lson
#define RSON tree[now].rson
#define MIDDLE ((left+right)>>1)
#define LEFT LSON,left,MIDDLE
#define RIGHT RSON,MIDDLE+1,right
void PushUp(int now)
{
tree[now].sum=tree[LSON].sum+tree[RSON].sum;//Number of numbers
tree[now].sum_=tree[LSON].sum_+tree[RSON].sum_;//Sum of the sum of each number
}
void UpDataMain(int num,int val,int &now,int left=1,int right=len)
//Modify, add val num in now
{
if(num<left||right<num)
{
return;
}
if(!now)
{
now=++point_cnt;
}
if(left==right)
{
tree[now].sum+=+val;
tree[now].sum_+=+val*val__[num];//Number of values * of principle to be added
return;
}
UpDataMain(num,val,LEFT);
UpDataMain(num,val,RIGHT);
PushUp(now);
}
int lowbit(int now)//lowbit for tree array
{
return now&-now;
}
int root[maxN];
void UpData(int top,int num,int val)//Add val num at the top
{
for(int now=top;now<=N;now+=lowbit(now))//Modification of tree array
{
UpDataMain(num,val,root[now]);
}
}
//Record the current node of the tree to be added
int GetSum()//Number of numbers in the current tree
{
int sum=0;
return sum;
}
long long GetSum_()//Sum of the number of current trees
{
long long sum=0;
return sum;
}
int GetSumLeft()//The number of left subtrees of the current tree
{
int sum=0;
return sum;
}
long long GetSum_Left()//Sum of the number of left subtrees of the current tree
{
long long sum=0;
return sum;
}
int GetSumRight()//The number of right subtrees of the current tree
{
int sum=0;
return sum;
}
long long GetSum_Right()//Sum of the number of right subtrees of the current tree
{
long long sum=0;
return sum;
}
void GetRootLeft()//Change node to left son
{
}
void GetRootRight()//Change node to right son
{
}
long long QueryMain(int k,int left=1,int right=len)//Main functions of query part
{
int sum=GetSum();//Get the number of current trees
if(left==right)//If it is a leaf node
{
return /*Number of current representations*/val__[left]*/*There are only sum numbers, and the maximum number is k, so take a min*/min(sum,k);
}
if(k>=sum)//If k is too big
{
return GetSum_();//Returns the sum of the number of current trees
}
int left_sum=GetSumLeft();//Number of left subtrees
if(left_sum>=k)//If it's greater than or equal to k, it's worse than the left subtree
{
GetRootLeft();
return QueryMain(k,left,MIDDLE);
}
//Or we'll have to find the right subtree
long long result=GetSum_Left();
GetRootRight();
return result+QueryMain(k-left_sum,MIDDLE+1,right);
}
void BeforeQuery(int place)//Preprocessing
{
for(int now=place;now;now-=lowbit(now))
{
}
}
long long Query(int place,int k)//query
{
BeforeQuery(place);//Preprocessing
return QueryMain(k);
}
void UpDataAdd(int left,int right,int num)//Modify, same as normal tree array
{
UpData(left,Hash[num],1);
UpData(right+1,Hash[num],-1);
}
int main()
{
scanf("%d%d",&M,&N);
int num_cnt=0;
REP(i,1,M)
{
scanf("%d%d%d",&s[i],&e[i],&p[i]);//Record discretization
sor[++num_cnt]=p[i];
}
sort(sor+1,sor+1+num_cnt);
sor[0]=-INF;
REP(i,1,num_cnt)
{
if(sor[i]!=sor[i-1])
{
Hash[sor[i]]=++len;
val__[len]=sor[i];
}
}
REP(i,1,M)
{
}
long long pre=1;
int x,a,b,c,k;
REP(i,1,N)
{
scanf("%d%d%d%d",&x,&a,&b,&c);
k=1+(a*pre+b)%c;//Calculate k by formula
pre=Query(x,k);//query
printf("%lld\n",pre);
}
return 0;
}
```

Method 2

Front cheese

1. Persistent line tree It can be used. Chairman tree To achieve.
2. Difference : optimization method 1

Concrete realization

It can be found that method 1 is very cumbersome, so you can use the chairman tree to maintain the number of times each number of prefixes appears, and then you can do a difference

Code

```#include<bits/stdc++.h>
#define REP(i,first,last) for(int i=first;i<=last;++i)
#define DOW(i,first,last) for(int i=first;i>=last;--i)
using namespace std;
const int maxN=3e5+7;
int N,M;
int sor[maxN];
long long hanum[maxN];
int p[maxN];
int tot=0;
map<int,int>Hash;

//It's useless to connect the number of places to be put in each position with this position like graph theory. It can be handled simply
struct Edge
{
}edge[maxN*2];
int cnt_edge=0;
#define VAL edge[_i_].val
{
edge[++cnt_edge].val=val;
}

struct Tree//Chairman tree
{
int lson,rson,sum;
long long sum_;
}tree[maxN*32];
#define LSON tree[now].lson
#define RSON tree[now].rson
#define MIDDLE ((left+right)>>1)
#define LEFT LSON,left,MIDDLE
#define RIGHT RSON,MIDDLE+1,right
#define NEW_LSON tree[new_tree].lson
#define NEW_RSON tree[new_tree].rson
int cnt_point=0;
void PushUp(int now)
{
tree[now].sum=tree[LSON].sum+tree[RSON].sum;
tree[now].sum_=tree[LSON].sum_+tree[RSON].sum_;
}
void UpData(int num,int val,int &new_tree,int now,int left=1,int right=tot)
{
if(num<left||right<num)
{
new_tree=now;
return;
}
new_tree=++cnt_point;
if(left==right)
{//It's similar to method one
tree[new_tree].sum=tree[now].sum+val;//Plus the number of numbers
tree[new_tree].sum_=tree[now].sum_+hanum[num]*val/*The number * the number*/;
return;
}
UpData(num,val,NEW_LSON,LEFT);
UpData(num,val,NEW_RSON,RIGHT);
PushUp(new_tree);
}
long long Query(int k,int now,int left=1,int right=tot)//The query is easy to write
{
if(k<=0)return 0;//Lazy to discuss by category
if(left==right)//Direct calculation to leaf node
{
return min(k,tree[now].sum)/*Take the small value of k and the number in the current tree*/*hanum[left];
}
if(k>=tree[now].sum)//If k is too big
{
return tree[now].sum_;
}
return Query(k,LEFT)+Query(k-tree[LSON].sum,RIGHT);
}
int root[maxN];//Record the root node of the tree at each location
int main()
{
scanf("%d%d",&M,&N);
int s,e;
REP(i,1,M)
{
scanf("%d%d%d",&s,&e,&p[i]);
sor[i]=p[i];
AddEdge(s,p[i],1);//Add edge to this number, same as difference, l position + 1,r+1 position - 1
}
sort(sor+1,sor+1+M);//Discretization
sor[0]=114154;
REP(i,1,M)
{
if(sor[i]!=sor[i-1])
{
Hash[sor[i]]=++tot;
hanum[tot]=sor[i];
}
}
int check;
REP(i,1,N)//Build up trees
{
{
check=1;//It starts from the last tree, and then changes itself
FOR(i)//Add a number to this number
{
check=0;
}
}
else
{
root[i]=root[i-1];//No, it's the same as the previous one
}
}
long long pre=1;
int x,a,b,c,k;
REP(i,1,N)
{
scanf("%d%d%d%d",&x,&a,&b,&c);
k=1+(a*pre+b)%c;//Calculate k
pre=Query(k,root[x]);
printf("%lld\n",pre);
}
return 0;
}
```

Compare two methods

The method 1 is more obvious and easy to get, but the time complexity of Nlog ⁡ 22nn \ log 〝 2nnlog22 N is easy to TLE, and the method 2 is easier to write, but it needs to use the difference, which can not be directly figured out, running much faster than method 1

75 original articles published, praised 23, visited 6032

Posted on Sat, 08 Feb 2020 07:56:25 -0800 by jahred