20/10/27 NOIP模拟赛

· · 个人记录

T1

维护子树最大次大链，dp转移即可。

T2

差分后一次调整相当于对两个点+1/-1，另外因为对4取模，还可以无代价指定两个数+4/-4。

最后差分序列要归零。

贪心匹配即可。

T3

容斥后只用求每个格子被经过总和即可。

每重复经过必然导致出现环。

如果这个环上其他点不看作重复，那么一个重复格子和一个环就是一一对应的。

设g(i)表示走i步形成大小为i的环的走法数。

这个可以用任意走i步回原点的方案数f(i)容斥得到。

于是总重复数就是\sum_i4^{n-i}g(i)(n-i+1) 。

T4

可以做到O(M)加元素更新。

但是要支持撤销。

一个暴力点的思路是根号重构。

如果可以离线的可以分治。

但是题解给出了一种支持在线且时空复杂度都极为优秀的做法。

因为我们只能维护加数且一段信息的方向对dp是无所谓的，所以选择栈形结构，每次加数把信息丢进栈B，如果需要删数且栈A为空则暴力把栈B的信息弹出加入A，这样抱着了A从栈顶到栈底就是原来的数列，每次删除操作删掉栈顶元素即可。（要维护两个栈从底到顶的每一个dp状态）

这样就完成了维护工作，对于查询，即合并两个栈顶的背包即可，可以用单调队列优化至O(m)。

总时间复杂度O(Q+QM)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int getint(){
    int summ=0,f=1;char ch;
    for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    if(ch=='-')f=-1,ch=getchar();
    for(;isdigit(ch);ch=getchar()) summ=(summ<<3)+(summ<<1)+ch-48;
    return summ*f;
}
const int N=1e5+5,M=505;
int m,ty,lasans,ans,Q,g[M*3],q[N],f[M];
struct O{
    int w,v;
    int f[M];
    O(){w=0;v=0;memset(f,-1,sizeof(f));f[0]=0;}
};
stack<O> A,B;

void Add(int wi,int vi){
    O las=B.top();
    O now=las;now.w=wi;now.v=vi;
    for(int i=0;i<m;i++) if(las.f[i]!=-1) now.f[(i+wi)%m]=max(now.f[(i+wi)%m],las.f[i]+vi);
    B.push(now);
}
void Del(){
    if(A.size()==1&&B.size()==1) return;
    if(A.size()>1) A.pop();
    else{
        while(B.size()!=1){
            O now=B.top();B.pop();
            O las=A.top();

            for(int i=0;i<m;i++) now.f[i]=las.f[i];
            for(int i=0;i<m;i++) if(las.f[i]!=-1) now.f[(i+now.w)%m]=max(now.f[(i+now.w)%m],las.f[i]+now.v);
            A.push(now);
        }
        A.pop();
    }
}
void Qu(int l,int r){
    O TopB=B.top();
    for(int i=0;i<m;i++) g[i]=g[i+m]=TopB.f[i];
    l+=m;r+=m;
    int h=1,t=0;
    for(int i=r;i>=l;i--){
        while(h<=t&&g[i]>=g[q[t]]) t--;
        q[++t]=i;
    }
    O TopA=A.top();
    for(int i=0;i<m;i++){
        if(TopA.f[i]!=-1&&g[q[h]]!=-1) ans=max(ans,TopA.f[i]+g[q[h]]);
        l--;r--;
        while(h<=t&&q[h]>r) h++;
        while(h<=t&&g[l]>=g[q[t]]) t--;
        q[++t]=l;
    }
    for(int i=l;i<=r;i++) ans=max(ans,TopB.f[i]);
    for(int i=l;i<=r;i++) ans=max(ans,TopA.f[i]);
}

signed main(){
    cin>>m>>ty;
    cin>>Q;A.push(O());B.push(O());
    while(Q--){
        int _t,_w,_v,_l,_r;
        _t=getint();_w=getint();_v=getint();_l=getint();_r=getint();
        if(ty==1){_w^=lasans,_v^=lasans,_l=(_l^lasans)%m,_r=(_r^lasans)%m;}
        if(_l>_r) swap(_l,_r);

        if(_t==1) Add(_w,_v);
        else Del();

        ans=-1;
        Qu(_l,_r);

        cout<<ans<<"\n";
        lasans=max(0ll,ans)%1000000000;
    }
    return 0;
}