2022HDU多校第五场

过程

开场12读了个假题，以为是找一个时间最短的跟后面排队，wa了两发反应过了是找一个人数最少的跟在后面排队，然后wa了一发没清空就过了，寄，开始演队友了。10智慧题，明牌的话先手应该赢面很大，那什么时候会输呢，发现叫的骰子数必须大于等于1，那么就只有一种会输的情况了，没玩过吹牛，题面看了好久才看懂，这下又在签到上浪费了时间。同时队友过了03签到再看06，于是我跟榜看07，推出了暴力的DP式子有卷积形式，于是叫自己的想法告诉队友让他去搓NTT去，自己将暴力打好准备对拍，期间队友06WA了，帮他看了看，没有发现什么问题，于是转向01，发现是珂朵莉树，于是迅速开码，码完已经快结束了交完T了一发，已经没有时间在改了。这期间队友码完07T了，于是我交他动态数组创建将从小到大合并改为启发式合并通过07，（队友好强，这下成辅助了）。快结束的时候队友发现06题读假了，增删改都算一次操作，而他只考虑了增删，这波我跟着他给的题意想确实没找出bug,原来是题读错了，不过原文描述着实有点抽象， “Now you can modify, add or delete one letter in 1 unit of time.”,这里modify 我们理解是跟前面，现在你可以修改了，增加或删除消耗一单位时间，但实际上是 现在你可以 修改，增加，删除，均消耗一单位时间，这下顶级理解了。

赛后发现自己01假了，区间和只能再开一个线段树维护，不能在珂朵莉树上维护，否则珂朵莉树复杂度就假了。

这次比赛启发式合并NTT已经算是第4道签到题了，已经人均NTT了，自己应更加扩充自己的知识库了。02需要使用非线性筛，甚至要更高级的，(学的杜教筛已经不配了)，04听人说是暴力可做，可惜没时间看了。总结下来就是题一定要读对，题读错了会浪费巨大时间，这次12浪费了一些时间，10阅读理解智慧题思考时间尚可，01假了属实是人菜了，唔，签到一定要更快更好，要倒在难题上。

题解

01

区间赋属性很容易联想到珂朵莉树，同时单点需要维护权值，此处必须再开线段树来记录，不能在珂朵莉树上维护权值，否则珂朵莉树退化为暴力。

那么在珂朵莉树上维护属性，每当属性更改时，对相应属性进行按时间差分来获得修改前后得到的权值，最后在线段树上单点求值再加上属性对应权值即可。需注意n为1e8，而q为1e5，故此处需要动态开点线段树。

int n,q;
int attr=0;
vector<ll>sum;
struct SEG{
    ll sum[maxm],tag[maxm];
    int lson[maxm],rson[maxm];
    int root,cnt;
    void clear(int &o){
        if(!o) return;
        sum[o]=tag[o]=0;
        clear(lson[o]);clear(rson[o]);
        o=0;
    }
    inline void up(int o){sum[o]=sum[lson[o]]+sum[rson[o]];}
    void down(int o,int l,int r){
        int mid=(l+r)>>1;
        ll tmp=tag[o];tag[o]=0;
        if(!lson[o]) lson[o]=++cnt;
        if(!rson[o]) rson[o]=++cnt; 
        sum[lson[o]]+=1LL*tmp*(mid-l+1);
        sum[rson[o]]+=1LL*tmp*(r-mid);
        tag[lson[o]]+=tmp;tag[rson[o]]+=tmp;
    }
    void update(int &o,int l,int r,int L,int R,ll val){
        if(!o) o=++cnt;
        if(L<=l&&r<=R){sum[o]+=val;tag[o]+=val;return;}
        if(tag[o])down(o,l,r);
        int mid=(l+r)>>1;
        if(L<=mid) update(lson[o],l,mid,L,R,val);
        if(mid<R) update(rson[o],mid+1,r,L,R,val);
        up(o);
    }
    ll query(int &o,int l,int r,int pos){
        if(!o) o=++cnt;
        if(l==r) {return sum[o];}
        if(tag[o]) down(o,l,r);
        int mid=(l+r)>>1;
        if(pos<=mid) return query(lson[o],l,mid,pos);
        else return query(rson[o],mid+1,r,pos);
    }
};

struct KDLTree{
    struct node{
        int l,r;mutable int c;
        bool operator < (const node x)const {
            return l<x.l;
        }
    };
    set<node>s;SEG T;
    void clear(){
        s.clear();
        T.clear(T.root);
        T.root=T.cnt=0;
    }
    void split(int x){
        auto it = s.lower_bound({x,0,0});
        if(it!=s.end()&&it->l==x) return;
        it--;
        int L=it->l,R=it->r;
        int C=it->c;
        s.erase(it);
        s.insert({L,x-1,C});
        s.insert({x,R,C});
    }
    set<node>::iterator find(int x){
        auto it=s.upper_bound({x,0,0});
        it--;return it;
    }
    void assign(int l,int r,int x){
        split(l);split(r+1);
        auto itl = s.lower_bound({l,0,0});
        auto itr = s.lower_bound({r+1,0,0});
        for(auto it=itl;it!=itr;it++){
            T.update(T.root,1,n,it->l,it->r,sum[it->c]);
        }
        s.erase(itl,itr);
        s.insert({l,r,x});
        T.update(T.root,1,n,l,r,-sum[x]);
    }
    void assign1(int pos,int x){
        auto it=find(pos);
        auto tmp=it;
        int l=inf,r=-1,y=it->c;
        while(it->c==y) {
            r=it->r;
            it++;
            if(it==s.end()) break;
        }
        it=tmp;
        while(it->c==y){
            l=it->l;
            if(it==s.begin()) break;
            it--;
        }
        assign(l,r,x);
    }
    ll query(int x){
        auto it=find(x);
        return sum[it->c]+T.query(T.root,1,n,x);
    }

}kdl;
void solve(){
    n=read();q=read();
    sum.clear();sum.resize(q+1);
    kdl.clear();attr=0;
    kdl.s.insert({1,n,0});
    ll last=0,ans=0;
    int n2=(n-1)/2;
    while(q--){
        int opt=read();
        int x,y,c,v;
        if(opt==1){
            x=read(),c=read();
            x=((x-1)^last)%n+1;
            c=((c-1)^last)%n2+1;
            ++attr;
            if(x>c && x+c<=n) kdl.assign(x-c,x+c,attr);
            else if(x<=c){
                int tmp=c-x+1;
                kdl.assign(1,x+c+tmp,attr);
            }else {
                int tmp=x+c-n;
                kdl.assign(x-c-tmp,n,attr);
            }
        }
        else if(opt==2){
            x=read(),y=read();    
            x=((x-1)^last)%n+1;
            y=((y-1)^last)%n+1;
            auto tmp=kdl.find(x);
            kdl.assign1(y,tmp->c);
        }
        else if(opt==3){
            x=read(),v=read();
            x=((x-1)^last)%n+1;
            auto tmp=kdl.find(x);
            sum[tmp->c]+=v;
        }
        else{
            x=read();x=((x-1)^last)%n+1;
            ans=kdl.query(x);
            printf("%lld/n",ans);
            last=ans&1073741823;
        }
    }
}

02

只会杜教筛，要被时代淘汰力

03

对每一层建一个入点和出点，该层所有点连向出点，入点连向该层所有点，然后出点向+-k层的入点相连，直接跑dijk最短路即可。

struct Dijkstra{
    bool vis[maxn];
    ll dis[maxn];
    struct node{
        ll dis;int id;
        bool operator < (const node &a)const{
            return dis>a.dis;
        }
    };
    priority_queue<node>q;
    vector<P>G[maxn];
    void add(int u,int v,int w){
        G[u].pb({v,w});
    }
    inline void clear(int n){rep(i,1,n) G[i].clear();}
    void Dijk(int st,int n){
        while(!q.empty()) q.pop();
        rep(i,1,n) vis[i]=0,dis[i]=linf;
        dis[st]=0;
        q.push((node){0,st});
        while(!q.empty()){
            int u=q.top().id;q.pop();
            if(vis[u]) continue;
            vis[u]=1;
            for(auto x:G[u]){
                int w=x.second,v=x.first;
                if(dis[v]>dis[u]+w){
                    dis[v]=dis[u]+w;
                    q.push((node){dis[v],v});
                } 
            }
        }
    }
}D1;
int n,k,p,st,ed;
int dp[maxn];
void dfs(int now,int fa,int dep){
    dp[now]=dep;
    for(auto x:D1.G[now]){
        if(x.first==fa) continue;
        dfs(x.first,now,dep+1);
    }
}
void solve(){
    cin>>n;
    rep(i,1,n-1){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        D1.add(u,v,w);
        D1.add(v,u,w);
    }
    scanf("%d %d",&k,&p);
    scanf("%d %d",&st,&ed);
    dfs(1,0,1);
    rep(j,1,n){
        int i=dp[j];
        int t1=(i<<1)+n,t2=(i<<1)-1+n;
        D1.add(t2,j,0);
        D1.add(j,t1,0);
        if(i>k) D1.add(t1,((i-k)<<1)-1+n,p);
        if(i+k<=n) D1.add(t1,((i+k)<<1)-1+n,p);
    }
    D1.Dijk(st,3*n);
    printf("%lld/n",D1.dis[ed]);
    D1.clear(n*3);
}

04

待补

06

待补

07

各个数相连形成若干个环，环间任意取，环内取套公式，
一个相关博客，由此将若干个环用NTT合并，合并时进行启发式合并，每次选两个长度最小的合并，最后可保证复杂度/(O(nlog^2n)/)

10

注意到双方明牌，且说话时骰子数必须大于等于1，那么在两个人都满足第三种特殊状态时，骰子数为0，此时先手必输，否则均为先后必胜。

int n;
set<int>s;
void solve(){
    cin>>n;int tmp;bool flag1=0,flag2=0;
    s.clear();
    rep(i,1,n) scanf("%d",&tmp),s.insert(tmp);
    if(s.size()==n) flag1=1;
    s.clear();
    rep(i,1,n) scanf("%d",&tmp),s.insert(tmp);
    if(s.size()==n) flag2=1;
    if(flag1&flag2) puts("Just a game of chance.");
    else puts("Win!");
}  

12

新来的人回去到人数最少且标号最小的队伍去，那么一个set维护正在排队的人，每次根据当前的时间，来判断哪些排队的人排完了，以此来更新各个队列的人数，S[i]表示队伍中有i人的队伍，动态维护这些STL即可。

int n,m;
struct node{
    ll ddl;int id;
};
bool operator < (node a,node b){
    if(a.ddl==b.ddl) return a.id<b.id;
    else return a.ddl<b.ddl;
}
set<node>s;
set<int>S[maxn];
int cnt[maxn];
struct Peo{
    ll a,s;
}p[maxn];
ll len[maxn];
bool cmp(Peo a,Peo b){
    return a.a<b.a;
}
void solve(){
    cin>>n>>m;
    rep(i,1,n) scanf("%lld %lld",&p[i].a,&p[i].s);
    sort(p+1,p+1+n,cmp);
    rep(i,1,m) S[0].insert(i);
    ll ans=0;int now=0;
    rep(i,1,n){
        if(s.size()>0){
            auto it=s.upper_bound((node){p[i].a,inf});
            while(it!=s.begin()){
                auto  x=*s.begin();
                s.erase(s.begin());
                S[cnt[x.id]].erase(S[cnt[x.id]].find(x.id));
                cnt[x.id]--;
                S[cnt[x.id]].insert(x.id);
                now=min(now,cnt[x.id]);
            }
        }
        int x=*S[now].begin();
        S[now].erase(x);
        cnt[x]++;
        S[now+1].insert(x);
        if(!S[now].size()) now++;
        len[x]=max(len[x],p[i].a)+p[i].s;
        s.insert((node){len[x],x});
    }
    rep(i,1,m) ans=max(ans,len[i]);
    s.clear();
    rep(i,1,m) cnt[i]=0,len[i]=0;
    rep(i,0,n) S[i].clear();
    printf("%lld/n",ans);
}