显示代码纯文本
#include<cstdio>
#include<iostream>
#include<vector>
#include<set>
using namespace std;
const int SIZEN=100010,INF=0x7fffffff/300;
int N;
int W[SIZEN];
vector<int> s[SIZEN];
void add(int fr,int to)
{
s[fr].push_back(to);
s[to].push_back(fr);
}
int fa[SIZEN]={0},pos[SIZEN],son[SIZEN],top[SIZEN],en[SIZEN];
int dep[SIZEN],siz[SIZEN];
set<pair<int,int>,greater<pair<int,int> > > down[SIZEN];
int totw=0;
void print_down(int i)
{
cout<<"i:"<<i<<endl;
set<pair<int,int>,greater<pair<int,int> > >::iterator it;
for(it=down[i].begin();it!=down[i].end();it++)
{
pair<int,int> a=*it;
cout<<a.first<<" "<<a.second<<endl;
}
}
void dfs(int x)
{
son[x]=0;dep[x]=dep[fa[x]]+1;
siz[x]=1;
for(int i=0;i<s[x].size();i++)
{
int v=s[x][i];
if(v==fa[x]) continue;
fa[v]=x;
dfs(v);
siz[x]+=siz[v];
if(siz[v]>siz[son[x]]) son[x]=v;
}
}
void make_tree(int x,int tp)
{
pos[x]=++totw;top[x]=tp;
if(son[x]) make_tree(son[x],tp),en[x]=en[son[x]];
if(!son[x]) en[x]=x;
for(int i=0;i<s[x].size();i++)
{
int v=s[x][i];
if(v==fa[x]||v==son[x]) continue;
make_tree(v,v);
}
}
class miku//线段树
{
public:
int l,r;
int maxl,maxr,sum;
}tr[SIZEN*4];
int PW[SIZEN]={0};
void built(int root,int l,int r)
{
tr[root].sum=0;
tr[root].maxl=tr[root].maxr=-INF;
tr[root].l=l;tr[root].r=r;
if(l==r) return;
int mid=(l+r)/2;
built(root*2,l,mid);built(root*2+1,mid+1,r);
}
void push(int root,int k,int be,int w,int fr)
{
set<pair<int,int>,greater<pair<int,int> > >::iterator it;
it=down[k].lower_bound(make_pair(be,fr));
if(it!=down[k].end()) down[k].erase(it);
down[k].insert(make_pair(w,fr));
it=down[k].begin();
pair<int,int> a=*it;
if(pos[a.second]==k) it++;
if(it!=down[k].end())
{
a=*it;
tr[root].maxl=tr[root].maxr=max(PW[k],a.first+PW[k]);
}
else tr[root].maxl=tr[root].maxr=PW[k];
tr[root].sum=PW[k];
}
void update(int root)
{
tr[root].maxl=max(tr[root*2].maxl,tr[root*2].sum+tr[root*2+1].maxl);
tr[root].maxr=max(tr[root*2+1].maxr,tr[root*2].maxr+tr[root*2+1].sum);
tr[root].sum=tr[root*2].sum+tr[root*2+1].sum;
}
void add_seg(int root,int k,int w,int be,int fr)
{
if(tr[root].r<k||tr[root].l>k) return;
if(tr[root].l==tr[root].r)
{
push(root,k,be,w,fr);
return;
}
add_seg(root*2,k,w,be,fr);add_seg(root*2+1,k,w,be,fr);
update(root);
}
miku get(int root,int l,int r)
{
miku re;
re.maxl=re.maxr=-INF;re.sum=0;
if(tr[root].r<l||tr[root].l>r) return re;
if(l<=tr[root].l&&tr[root].r<=r) return tr[root];
miku tem1=get(root*2,l,r),tem2=get(root*2+1,l,r);
re.maxl=max(tem1.maxl,tem1.sum+tem2.maxl);
re.maxr=max(tem2.maxr,tem2.sum+tem1.maxr);
re.sum=tem1.sum+tem2.sum;
return re;
}
void add_tr(int k,int w,int be)//对整棵树的down和链的修改
{
int tmp=w,v=k,fr=v;
PW[pos[k]]=w;
while(v!=0)
{
miku tem1=get(1,pos[top[v]],pos[en[v]]);
add_seg(1,pos[v],tmp,be,fr);
miku tem2=get(1,pos[top[v]],pos[en[v]]);
fr=top[v];v=fa[top[v]];
tmp=tem2.maxl;be=tem1.maxl;
}
}
void prepare()
{
dfs(1);
make_tree(1,1);
built(1,1,totw);
for(int i=1;i<=N;i++) PW[pos[i]]=W[i];
for(int i=1;i<=N;i++) add_tr(i,W[i],-INF);
}
int query(int x)
{
set<pair<int,int>,greater<pair<int,int> > >::iterator it;
int v=x;
int ans=W[x];
miku tem1;
int sum=0;
int be=v;
while(v!=0)
{
it=down[pos[v]].begin();
pair<int,int> a=*it;
if(a.second==be) it++;
if(it!=down[pos[v]].end())
{
a=*it;
if(a.second==v)
ans=max(ans,a.first+sum);
else ans=max(ans,a.first+sum+W[v]);
}
if(v!=en[v])
{
tem1=get(1,pos[v]+1,pos[en[v]]);
ans=max(ans,tem1.maxl+W[v]+sum);
}
if(v!=top[v])
{
tem1=get(1,pos[top[v]],pos[v]-1);
ans=max(ans,tem1.maxr+W[v]+sum);
sum+=tem1.sum;
}
sum+=W[v];
be=top[v];v=fa[top[v]];
}
return ans;
}
int main()
{
freopen("nt2011_travel_jzp.in","r",stdin);
freopen("nt2011_travel_jzp.out","w",stdout);
char C;
int now,A,B,Q,M,L,tmp;
scanf("%c",&C);
scanf("%d%d%d",&N,&M,&L);
scanf("%d%d%d%d",&now,&A,&B,&Q);
for(int i=1;i<=N;i++)
{
now=(now*A+B)%Q;tmp=now%10000;
now=(now*A+B)%Q;
if(now*2<Q) tmp*=-1;
W[i]=tmp;
}
for(int i=1;i<N;i++)
{
now=(now*A+B)%Q;
tmp=(i<L)?i:L;
add(i-now%tmp,i+1);
}
prepare();
for(int i=1;i<M;i++)
{
now=(now*A+B)%Q;
if(now*3<Q)
{
now=(now*A+B)%Q;
int ans=query(now%N+1);
printf("%d\n",ans);
}
else
{
now=(now*A+B)%Q,tmp=now%10000;
now=(now*A+B)%Q;
if(now*2<Q) tmp*=-1;
now=(now*A+B)%Q;
add_tr(now%N+1,tmp,W[now%N+1]);
W[now%N+1]=tmp;
}
}
return 0;
}
mikumikumi