先把序列建好，然后区间插入、单点询问等价于在左端点插入，在右端点删除，然后前缀询问。
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define N 100001
typedef long long ll;
vector<int>tong[N];
typedef vector<int>::iterator ER;
struct Node{int v,lc,rc;ll sumv;}T[N*48];
int e=1,root[N<<1],pos[N];
struct Point{int v,p;}t[N];
bool operator < (Point a,Point b){return a.v<b.v;}
int ma[N],zy;
void BuildTree(int cur,int l,int r)
{
if(l==r) return;
int m=(l+r>>1);
T[cur].lc=++e;
BuildTree(T[cur].lc,l,m);
T[cur].rc=++e;
BuildTree(T[cur].rc,m+1,r);
}
void InsDel(int pre,int cur,int p,int v,int l,int r)
{
if(l==r)
{
T[cur].v=T[pre].v+v;
T[cur].sumv=T[pre].sumv+(ll)(ma[p]*v);
return;
}
int m=(l+r>>1);
if(p<=m)
{
T[cur].lc=++e;
T[cur].rc=T[pre].rc;
InsDel(T[pre].lc,T[cur].lc,p,v,l,m);
}
else
{
T[cur].rc=++e;
T[cur].lc=T[pre].lc;
InsDel(T[pre].rc,T[cur].rc,p,v,m+1,r);
}
T[cur].v=T[T[cur].lc].v+T[T[cur].rc].v;
T[cur].sumv=T[T[cur].lc].sumv+T[T[cur].rc].sumv;
}
ll Query(int cur,int K,int l,int r)
{
if(l==r) return (ll)K*(ll)ma[l];
int m=(l+r>>1);
ll res=0;
if(T[T[cur].lc].v>=K) res+=Query(T[cur].lc,K,l,m);
else
{
res+=T[T[cur].lc].sumv;
res+=Query(T[cur].rc,K-T[T[cur].lc].v,m+1,r);
}
return res;
}
int m,n,Xs[N],Ys[N],Vs[N];
ll Ans=1;
int Abs(int x){return x<0?(-x):x;}
int rs;
int main()
{
ll A,B,C; int X;
scanf("%d%d",&m,&n);
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&Xs[i],&Ys[i],&t[i].v);
t[i].p=i;
}
sort(t+1,t+m+1);
Vs[t[1].p]=++zy;
ma[zy]=t[1].v;
for(int i=2;i<=m;++i)
{
if(t[i].v!=t[i-1].v) ++zy;
Vs[t[i].p]=zy;
ma[zy]=t[i].v;
}
for(int i=1;i<=m;++i)
{
tong[Xs[i]].push_back(Vs[i]);
if(Ys[i]!=n) tong[Ys[i]+1].push_back(-Vs[i]);
}
root[0]=1;
BuildTree(root[0],1,zy);
for(int i=1;i<=n;++i)
{
for(ER j=tong[i].begin();j!=tong[i].end();++j)
{
++rs; ++e; root[rs]=e;
InsDel(root[rs-1],root[rs],Abs(*j),(*j)>0?1:(-1),1,zy);
}
pos[i]=rs;
}
for(int i=1;i<=n;++i)
{
scanf("%d%ll%lld%lld",&X,&A,&B,&C);
int K=1+(int)((((A%C)*(Ans%C))%C)+(B%C))%C;
if(T[root[pos[X]]].v<K) printf("%lld\n",Ans=Query(root[pos[X]],T[root[pos[X]]].v,1,zy));
else printf("%lld\n",Ans=Query(root[pos[X]],K,1,zy));
}
return 0;
}转载于:https://www.cnblogs.com/autsky-jadek/p/4422322.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/109487.html原文链接：https://javaforall.net
