不知道写什么题了，那就来刷东方题单吧！

绿以下的题被以前的我秒完了，所以从绿开始写。

大概只会做简单题。

题目按照我做的顺序排列。

题单

Manipulating History

被 *1700 的诈骗创飞了。

思考的时候一直在从字符串匹配的角度出发，然后啥也想不出来。

想贪心也贪不动，因为保证唯一解所以没东西能贪。

中间想到过一点正确思路：起始的那个字母在后面没有出现过。

但是瞬间弃掉了。

事实上，我们只需要关心每个字母的出现次数即可。

开始的那个字母在所有的字符串中一定出现了奇数次，其他字母一定都出现了偶数次。

证明也是容易的：

把最终字符串当成一次操作，删除整串，并添加空串，则所有字母出现的次数都是 0（偶数）。

开始时只有一个字母出现次数为奇数，即中间的改变次数为奇数，其他字母的改变次数为偶数。

即开始的那个字母在所有的字符串中一定出现了奇数次，其他字母一定都出现了偶数次。

琪露诺

单调队列优化 DP 模板题。

上白泽慧音

强连通分量模板题。

红色的幻想乡

疑似学高级数据结构学傻了，树套树做不了就没思路了。

十字取反，矩形求和，听上去是不是非常不可做？

事实上，我们只需要对行和列分别维护一颗线段树即可。

因为一个点的状态只和它所在的行和列的操作次数的奇偶性有关：若行和列的操作次数的奇偶性相同，则这个点为 0，否则为 1。

所以只需要分别维护每行和每列的操作次数的奇偶性即可。

此时十字取反变成了单点取反，矩形求和变成了区间求和。

做完了。

小魔女帕琪

我是期望低手，让我做期望不如沙了我。

首先加强一下，把 7 种改成 $n$ 种。

设 $sum=\sum_{i=1}^n a_i$。

根据期望的线性性，我们可以用所有方案的总贡献除以方案数得到期望。

方案数是好算的，就是一个多重集的排列数。

然后考虑贡献。

我们考虑每个长度为 $n$ 的区间带来的贡献。显然每个区间都是相同的，所以只需要考虑一个然后乘上区间数量即可。

因为每个长度为 $n$ 的区间贡献都是 1，所以依旧算方案数即可。

因为要这个保证这个区间是合法的，所以必须每种元素有一个，方案数为 $n!$。

剩下位置可以乱填，又是一个多重集的排列数。

最后乘上区间数量即可。

所以答案为

$$\frac {n!\times \frac{(sum-n)!}{\prod_{i=1}^n (a_i-1)!}\times (sum-n+1)}{\frac{sum!}{\prod_{i=1}^na_i!}}$$

化简一下，可以得到

$$\frac {n!\times \prod_{i=1}^na_i}{sum^{\underline{n-1}}}$$

下划线代表下降幂。

SAC E#1 - 一道难题 Tree

1.考虑最小割。

建一个汇点，把所有叶子向汇点连边，然后直接求最小割即可。

为什么这么做就是对的？

因为一棵树中，任意两点间有且只有一条简单路径，所以只需要把根到叶子的路径上的任意一条边割掉即可，所以求最小割就是对的。

2.考虑 DP。

加强版：[SDOI2011] 消耗战

设 $f_u$ 表示根和以 $u$ 为根子树不连通的最小代价，$mn_u$ 表示根到 $u$ 路径上的最小边权，转移为

$$f_u=\min(mn_u,\sum_{v\in sub_u} f_v)$$

复杂度 $O(n)$

三步必杀

区间加等差数列，常见做法是维护差分，这样就变成对差分数组区间加了。

但是这道题复杂度要求 $O(n)$，不能直接线段树。

不过没有一边修改一边查询，而是只有最后有一次查询，所以区间加可以差分一下变成单点加。

因为做了两次差分，所以最后做两遍前缀和即可复原。

萃香的请柬

考验选手观察能力。

如果把题目中给的图继续往下写几行，就可以发现：序列的长度是斐波那契数列，1 的个数也是斐波那契数列。

然后查询只需要差分一下即可。

那题目里给的初始状态呢？没有用吗？

是的。

这是因为无论初始状态是什么样，在经过无限长的时间后，序列都和一开始只有一个 1 的状态是一样的。

查询时的拆分为什么正确？

因为根据齐肯多夫定理：任意正整数可以被拆分为若干个不连续的 Fibonacci 数之和。

这个东西在 [SNOI2020] 取石子 中也有使用（斐波那契进制下的数位 DP）。

[BJWC2012] 冻结

分层图最短路模板题。

分成 $k$ 层，每向下走一层代表用一张卡，最后对每一层的终点距离取 $\min$ 即可。

OIer们的东方梦

刚学搜索的时候做的题，现在怎么升蓝了。

写一个堆优化的 BFS 就可以过了。

没啥思维量，就是代码比较难写，细节比较多。

荷取融合

又 是 期 望。

依旧根据期望的线性性，先算总贡献，再算方案数。

我们把题目中的游戏转化一下，从另一个角度考虑。

我们把题目中的向右走和停下拆开，拆成每次只能向右走一步和在当前格停下。

可以发现，我们只有在停下时才会有收益。

设 $f_{i,j}$ 表示前 $i$ 格停下了 $j$ 次的方案数，$g_{i,j}$ 表示前 $i$ 格停下了 $j$ 次的总收益，转移为

$$f_{i,j}=f_{i-1,j}+f_{i,j-1} \\ g_{i,j}=g_{i-1,j}+g_{i,j-1}\times a_i$$

转移容易理解，就是从上一格走过来或者在当前格停下，停下时可以获得收益。

那么为什么这种理解方式和之前那种游戏的操作是对应的？

事实上，我们只是把之前的向右移动若干步并停下拆成了向右移动一步和停下。

而且我们的每一次停下都对应原来的一次操作，这就一一对应了。

答案为 $\frac {g_{n,k}}{f_{n,k}}$。

需要滚动数组。

回忆京都

啥玩意，这是来搞笑的吗。

预处理组合数，然后求前缀和，没了啊？

一开始还以为读错题了，这能有绿啊？

[Cnoi2019] 数学作业

第一眼以为是高维前缀和，然后不会了。

什么时候才能记住位运算的每一位是独立的！！！

既然是异或，那我们按位考虑。

假设当前考虑到第 $k$ 位，那我们把所有数的第 $k$ 位拿出来。现在就是要求这个 01 序列的所有子集的异或和的和。

如果整个序列都是 0，那么答案显然是 0。

如果有至少一个 1，那么我们可以特殊的考虑其中的一个 1。

剩下的 $n-1$ 个元素一共有 $2^{n-1}$ 种选法。而无论哪种选法，我们都可以控制这个特殊的 1 选不选来让这种选法产生贡献。

所以一共会产生 $2^{n-1}\times 2^k$ 的贡献。

最后把这些贡献加起来就是对的。

事实上，我们只需要把所有数都或起来，然后乘 $2^{n-1}$ 就是答案（想一想为什么）。

「Wdsr-1」小铃的书

学到了没用的新技巧：如何开桶。

第一想法是开桶记录每种数出现个数。

但是值域让我们无法做到这一点。

离散化也不行，我们做不到存下来这些数。

但有一个性质：一个数的出现次数和这个数在另一个进制下每一位上的数字的出现次数相同。

这很好理解，就是把这个数换了个进制表示而已。

这非常好：因为我们能开的下桶了。

这里我选了 100 进制，已经足够用了（$10^{18}=100^9$）。

以下是一份没有加快读的代码，无法通过。

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=10,base=100;
int n,k;
int buc[maxn][base];
inline int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a;
        b>>=1;
        a=a*a;
    }
    return res;
}
inline void add(int x){
    int len=0;
    while(x){++buc[len++][x%base],x/=base;}
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(re int i=1,x;i<=n;++i) cin>>x,add(x);
    int ans=0;
    for(re int i=0;i<=9;++i){
        for(re int j=0;j<=99;++j){
            buc[i][j]%=k;
            if(!buc[i][j]) continue;
            ans+=qpow(base,i)*j;
        }
    }
    cout<<ans;
    return 0;
}

「Wdoi-1」加密通信

好吧，又想少了。

可以发现，$B_i=\gcd(A_i,A_{i-1})$。

所以直接算就行了？

显然不对，如果 $A_{i-1}=A_i$ 就寄了。

但题目保证了存在 $A_i \neq A_j$，所以找出来相邻的两个不同的数算出来 $\gcd$ 然后往两边推出来所有 $B$ 即可。

「Wdsr-2」间歇泉

这不是我们 CSP-S 2024 一轮的 序列合并 吗？

容易想到二分答案，然后转化成数数问题。

设当前二分到 $mid$，则需要数 $\frac {a_ic_i+a_jc_j}{a_i+a_j}\ge mid$ 的点对 $(i,j)$ 的对数。

移项，得到 $a_i\times (c_i-mid)\ge a_j\times (mid-c_j)$。

设 $A_i=a_i\times (c_i-mid),B_i=a_i\times (mid-c_i)$。

那么现在问题转化成了求 $A_i \ge B_j$ 的点对 $(i,j)$ 的对数。

这是经典问题，排序后双指针即可（也可以树状数组，感觉更好写，不过这题是浮点数用不了树状数组）。

「Wdsr-2.5」琪露诺的算数游戏

大模拟。

所以我写了这道题。

总用时约 1.5 h。

一些注意事项：

1. 变量名别写错。
2. 不知道为什么 stoi 寄了，所以需要手写 string 转 int。
3. 除法向上取整在负数情况下会寄，需要用 floor。
4. double 状态的人在出完第一张基本牌时要把 double 状态清掉。
5. 仔细读题，别漏细节。

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=35,maxm=3e5+10,K=99,inf=1e18;
int n,m,k;
int turn,now,nowp,nowpai;
inline int to_int(string s){
    int res=0;
    for(re int i=0;i<s.length();++i) res=res*10+(s[i]-'0');
    return res;
}
struct card{
    string name;
    int op,x;
    inline void init(){
        if(name=="PASS") op=6;
        else if(name=="TURN") op=7;
        else if(name=="DOUBLE") op=8;
        else{
            string s="";
            for(re int i=1;i<name.length();++i) s+=name[i];
            x=to_int(s);
            if(name[0]=='A') op=1;
            if(name[0]=='B') op=2;
            if(name[0]=='C') op=3;
            if(name[0]=='D') op=4;
            if(name[0]=='E') op=5;
        }
    }
}t[maxm];
struct player{
    string name;
    card c[4];
    bool op;
}p[maxn];
inline void end_turn(int id){
    p[now].c[id]=t[nowpai++];
    now=(now+turn)%n;if(!now) now=n;
}
inline bool solve2(){
    int nxtp=0,mxp=-inf,id=0,cnt=0;
    for(re int j=1;j<=3;++j){
        if(p[now].c[j].op<=5){
            ++cnt;
            if(p[now].c[j].op==1){
                nxtp=nowp+p[now].c[j].x;
                if(nxtp<=K){
                    if(mxp<nxtp) mxp=nxtp,id=j;
                    else if(mxp==nxtp){
                        if(p[now].c[id].op==2||p[now].c[id].op==4||p[now].c[id].op==5) id=j;
                    }
                }
            }
            if(p[now].c[j].op==2){
                nxtp=nowp-p[now].c[j].x;
                if(nxtp<=K){
                    if(mxp<nxtp) mxp=nxtp,id=j;
                    else if(mxp==nxtp){
                        if(p[now].c[id].op==4||p[now].c[id].op==5) id=j;
                    }
                }
            }
            if(p[now].c[j].op==3){
                nxtp=nowp*p[now].c[j].x;
                if(nxtp<=K){
                    if(mxp<nxtp) mxp=nxtp,id=j;
                    else if(mxp==nxtp){
                        if(p[now].c[id].op==1||p[now].c[id].op==2||p[now].c[id].op==4||p[now].c[id].op==5) id=j;
                    }
                }
            }
            if(p[now].c[j].op==4){
                nxtp=floor(1.0*nowp/p[now].c[j].x);
                if(nxtp<=K){
                    if(mxp<nxtp) mxp=nxtp,id=j;
                    else if(mxp==nxtp){
                        if(p[now].c[id].op==5) id=j;
                    }
                }
            }
            if(p[now].c[j].op==5){
                nxtp=p[now].c[j].x;
                if(nxtp<=K){
                    if(mxp<nxtp) mxp=nxtp,id=j;
                    else if(mxp==nxtp){}
                }
            }
        }
    }
    if(mxp==-inf){
        if(cnt==3){
            for(re int j=1;j<=3;++j) p[now].c[j]=t[nowpai++];
            cout<<p[now].name<<" lost the game.\n";
            return 0;
        }
        else{
            int id1=0,id2=0,id3=0;
            for(re int j=1;j<=3;++j){
                if(p[now].c[j].op==6) id1=j;
                if(p[now].c[j].op==7) id2=j;
                if(p[now].c[j].op==8) id3=j;
            }
            if(id1){
                cout<<p[now].name<<" used "<<p[now].c[id1].name<<",now p="<<nowp<<".\n";
                end_turn(id1);
            }
            else if(id2){
                turn*=-1;
                cout<<p[now].name<<" used "<<p[now].c[id2].name<<",now p="<<nowp<<".\n";
                end_turn(id2);
            }
            else if(id3){
                int nxt=(now+turn)%n;
                if(!nxt) nxt=n;
                p[nxt].op=1;
                cout<<p[now].name<<" used "<<p[now].c[id3].name<<",now p="<<nowp<<".\n";
                end_turn(id3);
            }
        }
    }
    else{
        nowp=mxp;
        cout<<p[now].name<<" used "<<p[now].c[id].name<<",now p="<<nowp<<".\n";
        end_turn(id);
    }
    return 1;
}
inline bool solve1(){
    int id1=0,id2=0,id3=0;
    for(re int j=1;j<=3;++j){
        if(p[now].c[j].op==6) id1=j;
        if(p[now].c[j].op==7) id2=j;
        if(p[now].c[j].op==8) id3=j;
    }
    if(id1){
        p[now].op=0;
        cout<<p[now].name<<" used "<<p[now].c[id1].name<<",now p="<<nowp<<".\n";
        end_turn(id1);
        p[now].op=1;
    }
    else if(id2){
        turn*=-1;
        p[now].op=0;
        cout<<p[now].name<<" used "<<p[now].c[id2].name<<",now p="<<nowp<<".\n";
        end_turn(id2);
        p[now].op=1;
    }
    else if(id3){
        p[now].op=0;
        cout<<p[now].name<<" used "<<p[now].c[id3].name<<",now p="<<nowp<<".\n";
        end_turn(id3);
        p[now].op=1;
    }
    else{
        int nxtp=0,mnp=inf,id=0;
        for(re int j=1;j<=3;++j){
            if(p[now].c[j].op<=5){
                if(p[now].c[j].op==1){
                    nxtp=nowp+p[now].c[j].x;
                    if(nxtp<=K){
                        if(mnp>nxtp) mnp=nxtp,id=j;
                        else if(mnp==nxtp){
                            if(p[now].c[id].op==3||p[now].c[id].op==5) id=j;
                        }
                    }
                }
                if(p[now].c[j].op==2){
                    nxtp=nowp-p[now].c[j].x;
                    if(nxtp<=K){
                        if(mnp>nxtp) mnp=nxtp,id=j;
                        else if(mnp==nxtp){
                            if(p[now].c[id].op==1||p[now].c[id].op==3||p[now].c[id].op==5) id=j;
                        }
                    }
                }
                if(p[now].c[j].op==3){
                    nxtp=nowp*p[now].c[j].x;
                    if(nxtp<=K){
                        if(mnp>nxtp) mnp=nxtp,id=j;
                        else if(mnp==nxtp){
                            if(p[now].c[id].op==5) id=j;
                        }
                    }
                }
                if(p[now].c[j].op==4){
                    nxtp=floor(1.0*nowp/p[now].c[j].x);
                    if(nxtp<=K){
                        if(mnp>nxtp) mnp=nxtp,id=j;
                        else if(mnp==nxtp){
                            if(p[now].c[id].op==2||p[now].c[id].op==1||p[now].c[id].op==3||p[now].c[id].op==5) id=j;
                        }
                    }
                }
                if(p[now].c[j].op==5){
                    nxtp=p[now].c[j].x;
                    if(nxtp<=K){
                        if(mnp>nxtp) mnp=nxtp,id=j;
                        else if(mnp==nxtp){}
                    }
                }
            }
        }
        if(mnp==inf){
            p[now].op=0;
            for(re int j=1;j<=3;++j) p[now].c[j]=t[nowpai++];
            cout<<p[now].name<<" lost the game.\n";
            return 0;
        }
        else{
            nowp=mnp;
            cout<<p[now].name<<" used "<<p[now].c[id].name<<",now p="<<nowp<<".\n";
            p[now].c[id]=t[nowpai++];p[now].op=0;
        }
        return solve2();
    }
    return 1;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for(re int i=1;i<=n;++i){
        cin>>p[i].name;
        cin>>p[i].c[1].name>>p[i].c[2].name>>p[i].c[3].name;
        p[i].c[1].init();p[i].c[2].init();p[i].c[3].init();
    }
    for(re int i=1;i<=k;++i) cin>>t[i].name,t[i].init();
    now=1;nowpai=1;
    for(re int i=1;i<=m;++i){
        cout<<"Round "<<i<<":"<<'\n';
        nowp=0;turn=1;
        while(1){
            if(p[now].op){if(!solve1()) break;}
            else{if(!solve2()) break;}
        }
    }
    return 0;
}

「Wdoi-3」夜雀 singing

做这题时 PTSD 了。

可以想到，先处理出每个人能走到的最左侧点和最右侧点，显然我们只需要考虑那些走不到合法点的区间。

那么此时转化成了最少点覆盖区间问题，也就是我调了三个小时的 CSP-S 2024 T2。

现在的问题是如何处理这个区间。

暴力处理是 $O(nm)$ 的，但是这里有很多重叠信息可以利用。

下面只考虑右端点怎么求，左端点同理。

我们把人的位置排序，从左向右考虑。

如果之前的人能走到的最远位置小于等于当前位置，那么让这个人暴力向右拓展。

否则，我们从之前的人能走到的最远位置开始暴力向右拓展。

每个位置最多被拓展一遍，所以复杂度是 $O(n+m)$ 的。

这个单调性还是挺好理解的吧，而且感觉这东西和 manacher 挺像的？

希望 NOIP 别再爆了。

别再爆了别再爆了别再爆了别再爆了别再爆了别再爆了。

「Wdoi-4」芙兰？姆Q！贤者与谜题

读完题以后第一想法是暴力建图然后变成 Minimal Labels 。

然而暴力建图会有 $O(nq)$ 条边，所以死掉了。

所以考虑优化建图。

容易发现，我们会建一堆重边，只要能去掉这些重边，边数就会变成 $O(n)$ 级别。

考虑使用并查集，连边时把父亲也更新。

因为需要正着连和反着连，所以需要两个并查集。

然后没了。

「Wdcfr-1」CONsecutive and CONcat (easy version)

小清新计数题。

但是非常容易算重。

把贡献分为两部分：自己产生的和若干串拼接产生的。

自己内部的贡献很好算，不再赘述。

在弱化版中，保证了一个串内至少包含两种不同的字母符，所以若干串拼接一定是两个串拼接。

设前一个串的后缀长度为 $suf$，后一个串的前缀长度为 $pre$。

直接算会算重：当 $k \le suf$ 或 $k \le pre$ 时，会有一些部分在同一个字符串中，但这部分贡献已经被计算过了。

这是前后两个串的后缀和前缀。

第一种情况：$k > suf,k > pre$

那么此时的合法位置数为 $(suf+pre-k+1)-1+1$。

第二种情况：$k \le suf$ 或 $k \le pre$

那么此时的合法位置数为 $suf-((suf+1)-k+1)+1$。

综上，合法方案数应为 $\min(suf+pre-k+1,suf)-\max(suf-k+2,1)+1$。

因为会贡献到 $(n-1)!$ 种排列中（捆绑法），所以还要乘上 $(n-1)!$。

实现时，我们不能 $O(n^2)$ 的枚举字符串，但 $m \le 100$，所以可以枚举前后缀长度。

但枚举前后缀长度时，如果一个字符串的前缀和后缀都是一个字符，可能会把它自己和自己拼接的贡献也算上，应该去掉。

这是一份 $O(n^2)$ 枚举字符串的代码：

#include"bits/stdc++.h"
#define re register
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=1e6+10,maxv=30,mod=998244353;
int n,m,k,ans;
int fac[maxn];
string s;
vector<pii> g1[maxv],g2[maxv];
inline void init(){
    fac[0]=1;
    for(re int i=1;i<=n;++i) fac[i]=fac[i-1]*i%mod;
}
inline void solve(int id){
    int pre=1;char c1=s[0];
    for(re int i=1;i<m;++i){
        if(s[i]!=c1) break;
        else ++pre;
    }
    g1[c1-'a'].push_back({id,pre});
    int suf=1;char c2=s[m-1];
    for(re int i=m-2;i>=0;--i){
        if(s[i]!=c2) break;
        else ++suf;
    }
    g2[c2-'a'].push_back({id,suf});
    int len=0;char lst=0;
    for(re int i=0;i<m;++i){
        if(s[i]!=lst){
            if(len>=k) ans=(ans+(len-k+1)*fac[n]%mod)%mod;
            lst=s[i],len=1;
        }
        else ++len;
    }
    if(len>=k) ans=(ans+(len-k+1)*fac[n]%mod)%mod;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;init();
    for(re int i=1;i<=n;++i){
        cin>>s;
        solve(i);
    }
    for(re int i=0;i<26;++i){
        for(auto x:g2[i]){
            for(auto y:g1[i]){
                if(x.fi==y.fi) continue;
                int suf=x.se,pre=y.se;
                if(suf+pre>=k) ans=(ans+(min(suf+pre-k+1,suf)-max(suf-k+2,1ll)+1)*fac[n-1]%mod)%mod;
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}

这是一份 $O(m^2)$ 枚举前后缀长度的代码：

#include"bits/stdc++.h"
#define re register
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=1e6+10,maxm=110,maxv=30,mod=998244353;
int n,m,k,ans;
int fac[maxn];
int pre1[maxm][maxv],suf1[maxm][maxv];
int a[maxm][maxm][maxv];
string s;
inline void init(){
    fac[0]=1;
    for(re int i=1;i<=n;++i) fac[i]=fac[i-1]*i%mod;
}
inline void solve(int id){
    int pre=1;char c1=s[0];
    for(re int i=1;i<m;++i){
        if(s[i]!=c1) break;
        else ++pre;
    }
    ++pre1[pre][c1-'a'];
    int suf=1;char c2=s[m-1];
    for(re int i=m-2;i>=0;--i){
        if(s[i]!=c2) break;
        else ++suf;
    }
    ++suf1[suf][c2-'a'];
    if(c1==c2) ++a[pre][suf][c1-'a'];
    int len=0;char lst=0;
    for(re int i=0;i<m;++i){
        if(s[i]!=lst){
            if(len>=k) ans=(ans+(len-k+1)*fac[n]%mod)%mod;
            lst=s[i],len=1;
        }
        else ++len;
    }
    if(len>=k) ans=(ans+(len-k+1)*fac[n]%mod)%mod;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;init();
    for(re int i=1;i<=n;++i){
        cin>>s;
        solve(i);
    }
    for(re int i=0;i<26;++i){
        for(re int pre=1;pre<=m;++pre){
            for(re int suf=max(k-pre,1ll);suf<=m;++suf){
                ans=(ans+(pre1[pre][i]*suf1[suf][i]-a[pre][suf][i])%mod*(min(suf+pre-k+1,suf)-max(suf-k+2,1ll)+1)%mod*fac[n-1]%mod)%mod;
            }
        }
    }
    cout<<ans;
    return 0;
}

「Wdcfr-1」CONsecutive and CONcat (hard version)

上一题的加强版。

现在可能出现这种东西：一个只由一种字符构成的字符串。

那么贡献要分为五种情况：

1. 单个串自己的贡献
2. 若干只由一种字符构成的字符串拼接
3. 一段后缀+若干只由一种字符构成的字符串
4. 若干只由一种字符构成的字符串+一段前缀
5. 一段后缀+若干只由一种字符构成的字符串+一段前缀

设 $f_{pre,num,suf}$ 表示前缀长度为 $pre$，中间有 $num$ 个只由一种字符构成的字符串，后缀长度为 $suf$ 的贡献。

那要怎么去重呢？

我不会啊？题解说的是啥？这是正常思路吗？难道正常思路不是钦定在某个地方算贡献吗？

等我以后再补。

upd：感谢 born_to_sun 的厉害思路。

具体请看洛谷题解，不在这里写了。

upd：原来 zak 也是这么写的。

「Wdsr-3」永远与须臾的走廊

怎么又是数数。

哦原来是性质题，竟然被我秒了。

通过手玩样例，可以发现：只要填出来的括号序列的任意一个循环同构是合法括号序列，那么这种方案就合法。

为什么？

这很好理解，因为我们要往后无限拼接，那么只要这个括号序列的任意一个循环同构是合法括号序列，那么就一定能拼出来合法的括号序列。

那么怎么判断这个括号序列的任意一个循环同构是合法括号序列呢？

可以发现：一个括号序列的任意一个循环同构是合法括号序列当且仅当它的左右括号数相等。

做完了。

[Cnoi2021] 数学练习

简单数数题。

对于 $S$ 大小为 $i$，$T$ 大小为 $n-i$ 时，$i$ 和 $n-i$ 要放的位置已经固定，只剩下 $n-2$ 个数可以随便放。

那么此时的方案数为 $\binom {n-2}{i-1}$。

需要特判 $n$ 为偶数，因为此时 $\frac {n}{2}$ 没地方放。

[Cnoi2021] 矩阵

简单式子题。

通过手推样例的 $k=1,2,3$，可以发现，答案为

$$(\sum_{i=1}^n a_i)\times (\sum_{i=1}^n b_i)\times (\sum_{i=1}^n a_ib_i)^{k-1}$$

需要特判 $k=0$。

还有注意取模，一定别取模少了（本来能一遍过就因为取模取少了）。

是不是写的太简短了？那我在这里推一下 $k=3$ 吧。

$$\begin{align*} ans &= \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n A'_{i,k}\times A_{k,j} \\ &=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n (\sum_{p=1}^n A_{i,p}\times A_{p,k}) \times A_{k,j} \\ &=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n (\sum_{p=1}^n a_i\times b_p\times a_p\times b_k) \times a_k\times b_j \\ &=\sum_{i=1}^n a_i\sum_{j=1}^n b_j\sum_{k=1}^n a_k\times b_k\sum_{p=1}^na_p\times b_p \\ &=(\sum_{i=1}^n a_i)\times (\sum_{i=1}^n b_i)\times (\sum_{i=1}^n a_ib_i)^2 \end{align*}$$

「Wdoi-5」模块化核熔炉

抽象坐标系。

如果是普通的矩形加，那树套树可以轻松解决。

但是这正六边形非常恶心啊，感觉根本做不了。

所以把坐标系变换一下，变成直角坐标系就能做了。

具体怎么变还是请参考题解吧，感觉有点抽象。

射命丸文的取材之旅

枚举区间显然不可做。

但值域是 $O(n)$ 的，所以可以枚举 $\operatorname{mex}$。

那么对于每个 $\operatorname{mex}$，我们找出它所在的最长区间即可。

假设我们的 $c$ 已经选好了，那么我们只需要把每个位置挂到值上，然后暴力找即可。

但现在我们需要决策一下 $a,b$。事实上这让我们的选择更加宽松了。

因为只有当 $a_i=b_i=\operatorname{mex}$ 时，我们才把这个位置挂到这个 $\operatorname{mex}$ 上。

每个位置只会遍历一次，复杂度 $O(n)$。

虹色的北斗七星

感觉在 CF 上见到过一车这种题？

如果这里的 $-len$ 是 $+len$，那么非常好做，因为这东西是有单调性的，直接枚举左端点然后二分右端点即可。

但这里不是，所以还把 $r-l+1$ 看成 $len$ 这个整体会很难做。

如果仔细思考会发现一个性质：最优区间的左右端点一定对应着 $\max$ 和 $\min$。

证明很容易：在不改变 $\max$ 和 $\min$ 的情况下扩大区间只能让收益减少。

所以，此时的 $l,r$ 一定对应着 $\max,\min$ 的下标。

分类讨论一下：

1. $l$ 对应 $\max$，$r$ 对应 $\min$。

式子变为 $(\max+l)-(\min+r)-1$。

设 $b_i=a_i+i$，那么要找的就是 $\max_{i\le j} b_i-b_j-1$。

扫的过程中维护前缀最大即可。

1. $r$ 对应 $\max$，$l$ 对应 $\min$。

式子变为 $(\max-r)-(\min-l)-1$。

设 $b_i=a_i-i$，那么要找的就是 $\max_{i\ge j} b_i-b_j-1$。

扫的过程中维护前缀最小即可。

复杂度 $O(n)$

[Aya Round 1 H] 破碎的历史

看到撤回还以为是操作树，结果是撤销单次操作。

仔细思考这个染色，可以发现：每次加进来的若干线段，只有那条最长的两端点均为黑点的线段是有用的。

那么要怎么维护是否合法？

我一开始想的是区间推平维护区间和，但是这东西完全没法撤销单次操作，如果是回到某个状态倒是能做，离线操作树+ [COCI2015-2016#3] NEKAMELEONI 即可。

那换个思路：非得维护区间和吗？

可以发现，如果一个点没被染过，那么它一定是 0。

所以维护最小值即可。

操作只需要普通的区间加，这东西显然可以撤销。

撤销单次操作加强版：方方方的数据结构

注意：区间加操作可能不合法，需要特判。

#include"bits/stdc++.h"
#define re register
#define int long long
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
using namespace std;
const int maxn=5e5+10,inf=1e18;
int n,m,rt,segcnt;
int a[maxn],b[maxn],pos[maxn];
struct tree{
    int ls,rs,tag,mn;
}tr[maxn<<1];
struct Query{
    int l,r;
}q[maxn];
inline void up(int p){tr[p].mn=min(tr[ls(p)].mn,tr[rs(p)].mn);}
inline void add(int l,int r,int val,int p){
    tr[p].mn+=val;
    tr[p].tag+=val;
}
inline void down(int l,int r,int mid,int p){
    if(tr[p].tag){
        add(l,mid,tr[p].tag,ls(p));
        add(mid+1,r,tr[p].tag,rs(p));
        tr[p].tag=0;
    }
}
inline void build(int l,int r,int &p){
    p=++segcnt;
    if(l==r){tr[p].mn=a[l];return;}
    int mid=(l+r)>>1;
    build(l,mid,ls(p)),build(mid+1,r,rs(p));
    up(p);
}
inline void update(int l,int r,int L,int R,int val,int p){
    if(L>R||L<=0||R>=n+1) return;
    if(l>=L&&r<=R){add(l,r,val,p);return;}
    int mid=(l+r)>>1;
    down(l,r,mid,p);
    if(L<=mid) update(l,mid,L,R,val,ls(p));
    if(R>mid) update(mid+1,r,L,R,val,rs(p));
    up(p);
}
inline int query(int l,int r,int L,int R,int p){
    if(l>=L&&r<=R) return tr[p].mn;
    int mid=(l+r)>>1,res=inf;
    down(l,r,mid,p);
    if(L<=mid) res=min(res,query(l,mid,L,R,ls(p)));
    if(R>mid) res=min(res,query(mid+1,r,L,R,rs(p)));
    return res;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1;i<=n;++i) cin>>pos[i];
    int len=0;
    for(re int i=1;i<=n;++i){
        cin>>a[i];
        if(a[i]) b[++len]=i;
    }
    build(1,n,rt);
    if(query(1,n,1,n,1)==0) cout<<"No\n";
    else cout<<"Yes\n";
    for(re int i=1,op,l,r,x;i<=m;++i){
        cin>>op;
        if(op==1){
            cin>>l>>r;
            l=lower_bound(pos+1,pos+n+1,l)-pos,r=upper_bound(pos+1,pos+n+1,r)-pos-1;
            l=b[lower_bound(b+1,b+len+1,l)-b],r=b[upper_bound(b+1,b+len+1,r)-b-1];
            update(1,n,l,r,1,1);
        }
        else{
            cin>>x;
            update(1,n,q[x].l,q[x].r,-1,1);
        }
        q[i]={l,r};
        if(query(1,n,1,n,1)==0) cout<<"No\n";
        else cout<<"Yes\n";
    }
    return 0;
}

「Wdoi-2」来自地上的支援

我是数据结构低手/kk。

遇到这种玩游戏题一般都要观察性质，否则按题意模拟复杂度肯定寄。

首先分析这个操作。

显然第三条规则是没用的，因为这种情况根本不可能出现。

然后可以发现一些性质：

1. 被选到的数的操作时刻一定是一段连续区间。
2. 如果一个数在第一次出现时没有被选上，那么它一定再也不会被选。

那么询问就很清楚了。

设 $c_i$ 表示第 $i$ 次操作后的 $\max_{j=1}^i b_j$。

第 $x$ 个数要想被选至少 $k$ 次，需要满足以下要求：

1.$a_x \ge c_{x-1}$

2.$a_x > \max_{i=x+1}^{x+k-1} a_i-(i-x)\times v$

第一个要求保证第 $x$ 个数第一次出现时就能被选上。

第二个要求保证第 $x$ 个数能被连续选 $k$ 次。

第一个要求很好处理，重点是第二个要求。

这个要求事实上就是这个问题：

给定公差 $d$，每次询问为区间加公差为 $d$ 的等差数列后的区间最大值。询问互相独立。

第一眼以为很不可做，但关键在公差不变上。

我们令 $a_i\leftarrow a_i+i\times d$，那么我们每次直接查区间最大值，查到的位置就是对的。

注意是位置，不是值。具体的值需要我们根据公差算一下才能得到。

把 $d$ 换成 $-v$ 就是这道题了。

实现时，我使用了 ST 表，空间复杂度 $O(n\log n)$，无法通过。换成线段树就行了。

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=2e6+10;
int n,m,v;
int a[maxn],b[maxn],c[maxn];
int st[22][maxn],id[22][maxn];
inline void pre(){
    for(re int i=1;i<=n;++i) b[i]=a[i];
    int mx=0,id=0;
    for(re int i=1;i<=n;++i){
        if(b[i]>=mx) id=i;b[id]+=v;
        c[i]=mx=b[id];
    }
}
inline void init(){
    for(re int i=1;i<=n;++i) st[0][i]=a[i]-i*v,id[0][i]=i;
    for(re int j=1;j<=21;++j){
        for(re int i=1;i<=n-(1<<j)+1;++i){
            if(st[j-1][i]>st[j-1][i+(1<<(j-1))]) st[j][i]=st[j-1][i],id[j][i]=id[j-1][i];
            else st[j][i]=st[j-1][i+(1<<(j-1))],id[j][i]=id[j-1][i+(1<<(j-1))];
        }
    }
}
inline int query(int l,int r){
    if(l>r) return 0;
    int k=__lg(r-l+1),pos=0;
    if(st[k][l]>st[k][r-(1<<k)+1]) pos=id[k][l];
    else pos=id[k][r-(1<<k)+1];
    return a[pos]-(pos-l+1)*v+1;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>v;
    for(re int i=1;i<=n;++i) cin>>a[i];
    pre();init();
    int ans1=0,ans2=0;
    for(re int i=1,x,k,res;i<=m;++i){
        cin>>x>>k;
        if(x+k-1>n) continue;
        res=max(c[x-1],query(x+1,x+k-1));
        ans1^=res,ans2+=res;
    }
    cout<<ans1<<" "<<ans2;
    return 0;
}

The Enchanted Forest

如果 $k \le n$，那么一定是选和最大的一个长度为 $k$ 的子区间。

还需要考虑新长出来的部分，这部分是固定的，为 $\frac {k\times (k-1)}{2}$。

如果 $k > n$，感性理解一下，可以发现：我们一定会把原来的都拿完，然后来回扫荡。

对于新长出来的那部分，因为我们要从一端走到另一端，所以会少拿 $\frac {n\times (n+1)}{2}$。

一共长出来了 $nk$ 个，所以这部分贡献为 $nk-\frac {n\times (n+1)}{2}$。

感觉说的非常不清楚啊，但我只会感性理解不会证明···

Doremy’s IQ

比上题简单。

正着似乎不太好考虑，所以我们倒着考虑。

通过观察样例可以发现，选一段极长后缀一定是一组合法解，这也启示我们倒着考虑。

所以我们倒着扫一遍，能选就选，选不了就停。

然后别忘了前缀里还有一些 $\le q$ 的是白送的，也要选上。

那么这为什么是对的呢？

我们正着来看上述操作，可以发现：我们优先让后面的扣，前面的能不扣就不扣。

感性理解一下，前面的越早扣，后面选择的余地就越小，所以能晚扣就晚扣。

然而在做题时我根本没证明，大概想了一下感觉对就做完了，不太会严谨证贪心啊。

Koishi Loves Segments

简单贪心。

做的时候睡着了，梦里会了。

直接贪就完事了，优先放长度短的，能放就放。

拿线段树模拟这个东西就行。

然后写代码的时候唐完了，离散化后点数为 $cnt$，我写个 $n$ 调半天没调出来，鉴定为睡晕了。

#include"bits/stdc++.h"
#define re register
#define int long long
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
using namespace std;
const int maxn=4e5+10,maxm=2e5+10,inf=1e18;
int n,m,rt,segcnt,ans;
int a[maxn],tmp[maxn];
struct node{
    int pos,x;
}t[maxn];
struct line{
    int l,r;
    inline bool operator < (const line &a)const{
        if(l==a.l) return r<a.r;
        return l>a.l;
    }
}lin[maxm];
struct tree{
    int ls,rs,mn,tag;
}tr[maxn<<1];
inline void up(int p){tr[p].mn=min(tr[ls(p)].mn,tr[rs(p)].mn);}
inline void add(int p,int val){
    tr[p].mn+=val;
    tr[p].tag+=val;
}
inline void down(int p){if(tr[p].tag) add(ls(p),tr[p].tag),add(rs(p),tr[p].tag);tr[p].tag=0;}
inline void build(int l,int r,int &p){
    p=++segcnt;
    if(l==r){tr[p].mn=a[l];return;}
    int mid=(l+r)>>1;
    build(l,mid,ls(p)),build(mid+1,r,rs(p));
    up(p);
}
inline void update(int l,int r,int L,int R,int val,int p){
    if(l>=L&&r<=R){add(p,val);return;}
    int mid=(l+r)>>1;
    down(p);
    if(L<=mid) update(l,mid,L,R,val,ls(p));
    if(R>mid) update(mid+1,r,L,R,val,rs(p));
    up(p);
}
inline int query(int l,int r,int L,int R,int p){
    if(l>=L&&r<=R) return tr[p].mn;
    int mid=(l+r)>>1,res=inf;
    down(p);
    if(L<=mid) res=min(res,query(l,mid,L,R,ls(p)));
    if(R>mid) res=min(res,query(mid+1,r,L,R,rs(p)));
    return res;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>m>>n;
    for(re int i=1;i<=m;++i) cin>>lin[i].l>>lin[i].r;
    for(re int i=1;i<=n;++i) cin>>t[i].pos>>t[i].x,tmp[i]=t[i].pos;
    sort(tmp+1,tmp+n+1);
    int cnt=unique(tmp+1,tmp+n+1)-(tmp+1);
    memset(a,0x3f,sizeof a);
    for(re int i=1;i<=n;++i){
        t[i].pos=lower_bound(tmp+1,tmp+cnt+1,t[i].pos)-tmp;
        a[t[i].pos]=min(a[t[i].pos],t[i].x);
    }
    for(re int i=1;i<=m;++i){
        lin[i].l=lower_bound(tmp+1,tmp+cnt+1,lin[i].l)-tmp;
        lin[i].r=upper_bound(tmp+1,tmp+cnt+1,lin[i].r)-tmp-1;
    }
    sort(lin+1,lin+m+1);
    build(1,cnt,rt);
    for(re int i=1;i<=m;++i) if(query(1,cnt,lin[i].l,lin[i].r,1)>0) update(1,cnt,lin[i].l,lin[i].r,-1,1),++ans;
    cout<<ans;
    return 0;
}

koishi的数学题

结论：$a \mod b=a-\lfloor \frac{a}{b} \rfloor \times b$。

推荐去做[清华集训2012] 模积和，加深一下印象。

第一眼以为模板整除分块，结果数据范围 $n \le 10^6$。

我们思考一下 $x$ 和 $x+1$ 的增量是什么。

可以发现，当 $i$ 为 $x+1$ 的约数时，$\lfloor \frac{x+1}{i} \rfloor$ 会比 $\lfloor \frac{x}{i}\rfloor$ 大 1。

因为还带了个 $\times i$，所以答案的增量就是 $x+1$ 的约数和。

这东西显然可以线性筛，然后做完了。

注意：我们求的是增量，所以还得求个前缀和。

不是哥们，怎么随便一交就最优解了？

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e6+10;
int n,cnt;
int pri[maxn],d[maxn];
bitset<maxn> vis;
inline void sieve(){
    d[1]=1;
    for(re int i=2;i<=n;++i){
        if(!vis[i]) pri[++cnt]=i,d[i]=i+1;
        for(re int j=1;j<=cnt&&i*pri[j]<=n;++j){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0){d[i*pri[j]]=(d[i]-d[i/pri[j]])*pri[j]+d[i];break;}
            else d[i*pri[j]]=d[i]*d[pri[j]];
        }
    }
    for(re int i=2;i<=n;++i) d[i]+=d[i-1];
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    sieve();
    for(re int i=1;i<=n;++i) cout<<n*i-d[i]<<" ";
    return 0;
}

萃香抱西瓜

读完题就想到了这道题：HDU 7446 梦中的地牢战斗。

看到这数据范围应该能直接想到暴力状压吧。

设 $f_{x,y,T,S}$ 表示当前在 $(x,y)$，时间为 $T$，拿到的西瓜状态为 $S$ 的最少次数。

转移就是从不走或者走一步转移来。

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=6,maxt=110,maxm=(1<<10)+10,inf=1e18;
int h,w,T,sx,sy,n,m,sum,S,ans;
int mp[maxn][maxn][maxt];
int f[maxn][maxn][maxt][maxm];
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>h>>w>>T>>sx>>sy>>n>>m;S=(1<<m)-1;
    for(re int i=1,t1,t2,op;i<=n;++i){
        cin>>t1>>t2>>op;
        sum+=op;
        for(re int t=t1,x,y;t<t2;++t){
            cin>>x>>y;
            if(!op) mp[x][y][t]=-1;
            else mp[x][y][t]=1<<(sum-1);
        }
    }
    if(mp[sx][sy][1]==-1){cout<<-1;return 0;}
    memset(f,0x3f,sizeof f);
    f[sx][sy][1][mp[sx][sy][1]]=0;
    for(re int t=2;t<=T;++t){
        for(re int x=1;x<=w;++x){
            for(re int y=1;y<=h;++y){
                if(mp[x][y][t]==-1) continue;
                if(mp[x][y][t-1]!=-1) for(re int s=0;s<=S;++s) f[x][y][t][s|mp[x][y][t]]=min(f[x][y][t][s|mp[x][y][t]],f[x][y][t-1][s]);
                for(re int i=0;i<4;++i){
                    int prex=x+dx[i],prey=y+dy[i];
                    if(prex<1||prex>w||prey<1||prey>h) continue;
                    if(mp[prex][prey][t-1]==-1) continue;
                    for(re int s=0;s<=S;++s) f[x][y][t][s|mp[x][y][t]]=min(f[x][y][t][s|mp[x][y][t]],f[prex][prey][t-1][s]+1);
                }
            }
        }
    }
    ans=inf;
    for(re int x=1;x<=w;++x){
        for(re int y=1;y<=h;++y){
            ans=min(ans,f[x][y][T][S]);
        }
    }
    cout<<(ans==inf?-1:ans);
    return 0;
}

冰精冻西瓜

这种题我竟然想了大于 0.5 h，还是水平太低了。

先考虑序列怎么做。

设 $pre_u$ 为前缀积。

对于一次修改中所有会受影响的点 $v$，它会加上 $\frac {pre_v}{pre_u}\times w$。

所以一个点的点权为 $val_v=\sum_{i=1}^m \frac {pre_v}{pre_{u_i}}\times w_i$。

把 $pre_v$ 提出来，得到 $val_v=pre_v\times \sum_{i=1}^m \frac {w_i}{pre_{u_i}}$。

对于每次修改，后面那个东西都是确定的，所以修改就是区间加。

但是有个问题：有 0 怎么办？

显然 0 的出现会让上面的操作出错。

但可以发现：如果有 0，那么这前后两段是完全独立的（即对前面段的操作不会影响到后面段，反之同理）。

所以以 0 为断点，把序列分成若干连续段，那么每个连续段是独立的。

对每个连续段分别做上面的东西即可。

然后上树是简单的，这题是子树加单点查，甚至不需要树剖。

根据 0 把原树拆成森林，然后对每部分分别做即可。

代码感觉非常好写，最大难点可能是精度问题？

妖梦斩木棒

一个比较麻烦的做法。

首先可以想到线段树，然后考虑怎么合并信息。

我们对每个节点维护：左/右侧 X 极长连续段长度，左侧第一个 ‘)’ 的位置，右侧第一个 ‘(‘ 的位置，该区间左右端点，该区间答案。

两个区间合并能产生新答案，当且仅当：左区间的右端点-右侧 X 极长连续段长度=右侧第一个 ‘(‘ 的位置且右区间的左端点+左侧 X 极长连续段长度=左侧第一个 ‘)’ 的位置。

事实上我写麻烦了，只需要对每个点维护左/右侧第一个 ‘)’ 的位置以及左/右侧第一个 ‘(‘ 的位置即可。

大家可以思考一下怎么做。

#include"bits/stdc++.h"
#define re register
#define int long long
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
using namespace std;
const int maxn=2e5+10,inf=1e18;
int n,m,rt,segcnt;
struct data{
    int ans;
    int l,r;
    int lpos,rpos;
    int len1,len2;
    inline data(){ans=len1=len2=0,lpos=inf,rpos=-inf;}
    inline void init(int val){
        if(val==-1) rpos=l,lpos=inf,len1=len2=ans=0;
        if(val==0) len1=len2=1,lpos=inf,rpos=-inf,ans=0;
        if(val==1) lpos=l,rpos=-inf,len1=len2=ans=0;
    }
    inline data operator + (const data &a)const{
        data res;
        res.l=l,res.r=a.r;
        res.ans=ans+a.ans;
        res.lpos=min(lpos,a.lpos);
        res.rpos=max(rpos,a.rpos);
        if(len1==r-l+1) res.len1=len1+a.len1;
        else res.len1=len1;
        if(a.len2==a.r-a.l+1) res.len2=len2+a.len2;
        else res.len2=a.len2;
        if(rpos==r-len2&&a.lpos==a.l+a.len1) ++res.ans;
        return res;	
    }
};
struct tree{
    int ls,rs;
    data s;
}tr[maxn<<1];
inline void up(int p){tr[p].s=tr[ls(p)].s+tr[rs(p)].s;}
inline void build(int l,int r,int &p){
    if(!p) p=++segcnt;
    tr[p].s.l=l,tr[p].s.r=r;
    if(l==r){
        if(l==1) tr[p].s.init(-1);
        else if(l==n) tr[p].s.init(1);
        else tr[p].s.init(0);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls(p)),build(mid+1,r,rs(p));
    up(p);
}
inline void update(int pos,int val,int p){
    if(tr[p].s.l==tr[p].s.r){tr[p].s.init(val);return;}
    int mid=(tr[p].s.l+tr[p].s.r)>>1;
    if(pos<=mid) update(pos,val,ls(p));
    else update(pos,val,rs(p));
    up(p);
}
inline data query(int L,int R,int p){
    if(tr[p].s.l>=L&&tr[p].s.r<=R) return tr[p].s;
    int mid=(tr[p].s.l+tr[p].s.r)>>1;
    //对于合并信息复杂的题，建议这么写，不然还得考虑你维护的信息的单位信息应该是什么（例如维护矩阵）
    if(R<=mid) return query(L,R,ls(p));
    if(L>mid) return query(L,R,rs(p));
    return query(L,R,ls(p))+query(L,R,rs(p));
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    build(1,n,rt);char c;
    for(re int i=1,op,l,r,pos;i<=m;++i){
        cin>>op;
        if(op==1){
            cin>>pos>>c;
            if(c=='(') update(pos,-1,1);
            if(c=='X') update(pos,0,1);
            if(c==')') update(pos,1,1);
        }
        else cin>>l>>r,cout<<query(l,r,1).ans<<'\n';
    }
    return 0;
}

Power收集

简单单调队列。

设 $f_{i,j}$ 表示当前在 $(i,j)$ 的最大价值，转移为

$$f_{i,j}=\max_{j-T\le k \le j+T} f_{i-1,k}+val_{i,j}$$

对每个 $i$ 都做一次单调队列即可。

小学数学题

第一遍没做出来···

首先 $n\le 15$，考虑状压，那么每次操作就是把至多 $r$ 位取反。

设 $f_S$ 表示到达状态 $S$ 的最小次数，转移为

$$f_S=\min f_T+1$$

发现这个转移很像最短路，且没有转移顺序，所以考虑用最短路转移。

暴力建图后跑最短路，复杂度为 $O(2^{2n})$。

按理来说过不了，但它过了。

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=(1<<15)+10,maxm=55,inf=1e18;
int n,m1,m2,r,S,cnt;
int dis[maxn],num[maxn];
bitset<maxn> vis;
vector<int> g;
struct limit1{
    int a,b;
}t1[maxm];
struct limit2{
    int a,b,c;
}t2[maxm];
inline void init(){
    for(re int s=0;s<=S;++s){
        bool flag=1;
        for(re int i=1;i<=m1;++i){
            bool a=s&(1<<(t1[i].a-1)),b=s&(1<<(t1[i].b-1));
            if(a^b){flag=0;break;}
        }
        if(!flag) continue;
        for(re int i=1;i<=m2;++i){
            bool a=s&(1<<(t2[i].a-1)),b=s&(1<<(t2[i].b-1)),c=s&(1<<(t2[i].c-1));
            if(!(b^c)&&(a^b)){flag=0;break;}
        }
        if(flag) g.push_back(s);
    }
}
inline bool check(int s,int t){
    int cnt=__builtin_popcount(s^t);
    return cnt<=r;
}
inline void spfa(){
    for(re int s=0;s<=S;++s) dis[s]=inf;
    queue<int> q;
    q.push(0);vis[0]=1,dis[0]=0,num[0]=1;
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=0;
        for(auto v:g){
            if(!check(u,v)) continue;
            if(dis[v]>=dis[u]+1){
                if(dis[v]==dis[u]+1) num[v]+=num[u];
                else num[v]=num[u];
                dis[v]=dis[u]+1;
                if(!vis[v]) q.push(v),vis[v]=1;
            }
        }
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m1>>m2>>r;r=min(r,n);S=(1<<n)-1;
    for(re int i=1;i<=m1;++i) cin>>t1[i].a>>t1[i].b;
    for(re int i=1;i<=m2;++i) cin>>t2[i].a>>t2[i].b>>t2[i].c;
    init();spfa();
    if(dis[S]==inf) cout<<-1<<' '<<0;
    else cout<<dis[S]<<' '<<num[S];
    return 0;
}

正解：

考虑优化建图。

我们把一个点拆成 $r+1$ 个点：一个真点（记作 $S_0$）和 $r$ 个假点（记作 $S_k$，表示还能和当前状态差 $k$ 位）。

我们这样建图：

1. $S_0$ 向 $S_r$ 连边权为 1 的边
2. $S_k$ 向 $T_{k-1}$ 连边权为 0 的边（$1\le k \le r$，$T$ 为和 $S$ 恰好差一位的状态）
3. $S_k$ 向 $S_0$ 连边权为 0 的边（$1\le k <r$）

复杂度 $O(n^2 2^n)$

但有个问题，最短路计数怎么记？

暂时不会。

题解做法正确性不显然，我也不会。

upd：这个做法好像求不了方案数。

大家看题解自己悟吧。

河城荷取的烟花

建图时，如果两条绳子有交点，要把交点独立出来。

建完图以后，从每个点跑一次最短路。

以一个点作为起点跑最短路后，可以得到每个点被点燃的最早时间。

然后枚举绳子，得到每条绳子燃烧完的时间。

注意中点不能作为点燃点。

复杂度取决于你怎么写最短路。

别写 SPFA 了。

帕秋莉的手环

加强版：花园

这道题先断环成链然后设个 $f_{i,0/1}$ 再把转移写出来发现能矩阵加速然后就做完了。

来看加强版。

根据弱化版的状态，我们应该把前 $m$ 个位置的状态都记下来。

又因为 $m\le 5$，所以考虑状压。

设 $f_{i,S}$ 从 $f_{i-1,T}$ 转移过来，考虑 $S,T$ 要满足什么限制，可以发现：

1. 状态 $S,T$ 里 $1$ 的个数 $\le k$
2. $T$ 的后 $m-1$ 位与 $S$ 的前 $m-1$ 位完全相同

代码实现上，可以这样写

$$f_{i,S}=f_{i-1,S>>1}+f_{i-1,(S>>1)|(1<<(m-1))}$$

关于断环成链的部分，对于初始状态 $f_{0,S}$，DP 后的 $f_{n,S}$ 就是答案（因为这是个环）。

容易发现这东西能用矩阵加速。

构造转移矩阵 $A$，其中 $A_{S,T}$ 表示状态 $S$ 能否转移到状态 $T$。

枚举初始状态和统计答案都不变，把 $O(n)$ 的递推改成 $O(\log n)$ 的矩阵快速幂即可。

设矩阵大小 $V=2^m$，则复杂度为 $O(2^mV^3+V^3\log n)$

[MtOI2019] 幻想乡数学竞赛

简单题，把通项求出来即可。

如果你不会求常系数线性递推方程的通项，可以看我的这篇文章。

带大家一起算一下吧。

先整理成标准形式

$$\begin{cases} a_n-3a_{n-1}-a_{n-2}+3a_{n-3}=3^n \\ a_0=-3,a_1=-6,a_2=-12 \end{cases}$$

其特征方程为

$$x^3-3x^2-x+3=0$$

其特征根为

$$x_1=-1,x_2=1,x_3=1$$

所以通解为

$$a_n=c_1\times (-1)^n+c_2+c_3\times 3^n$$

因为 $f_n$ 为指数函数，且 $3$ 为一重特征根，所以设特解 $H_n^{*}=Pn3^n$ 。

代入，得

$$Pn3^n-3P(n-1)3^{n-1}-P(n-2)3^{n-2}+3P(n-3)3^{n-3}=3^n$$

解得

$$P=\frac {9}{8}$$

通解为

$$a_n=c_1\times (-1)^n+c_2+c_3\times 3^n+\frac {1}{8}n3^{n+2}$$

将初值代进去，解得

$$\begin{cases} c_1=-\frac {15}{32} \\ c_2= \frac {9}{8} \\ c_3=- \frac {117}{32} \end{cases}$$

综上，通解为

$$a_n=-\frac {15}{32}\times (-1)^n+\frac {9}{8}- \frac {117}{32}\times 3^n+\frac {1}{8}n3^{n+2} \\ a_n=\frac {3^{n+2}(4n-13)+36-15(-1)^n}{32}$$

信仰收集

思考方向又反了啊···

题目中两种行走方式本质相同，我们下面只考虑一种：步长为 $k$。

设走一步的代价为 $val$。

不难想到 DP：设 $f_u$ 表示到达点 $u$ 的最大收益，则转移为

$$f_{u}=\max_{dis(v,u)=k} f_v+w_u-val$$

考虑如何快速维护到一个点距离恰好为 $k$ 的点集。

我的想法是：因为起点只有 1，所以可以给每个点维护若干条从 1 开始的长为 $k$ 的链。

但每个点最多会维护 $O(n)$ 条链，所以复杂度 $O(n^2 k)$，寄了。

感觉这东西真不太能做吧？

所以我们换个角度思考：既然我们无法维护出从哪转移来，那能不能维护点 $u$ 向后面点的贡献？

这似乎是可以维护的。

重新设计 DP：设 $f_{u,j}$ 表示从点 $u$ 还要走 $k$ 步的最大收益，设存在边 $(v,u)$，则转移为

$$f_{u,j}=\max_{1\le j < k} f_{v,j+1} \\ f_{u,0}=\max f_{v,1}+w_u \\ f_{u,k-1}=\max f_{v,0}-val$$

这个 DP 的思路是：我们从点 $v$ 往后走，即先把代价减去。如果能贡献到答案，那么它一定会走到后面的一个点然后把答案贡献上去。

一定要初始成极小值，因为我们需要接受答案为负数（刚减去代价时）。

注意特判 $k=1$。

复杂度 $O(nk)$

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=2e5+10,maxm=3e5+10,maxk=55;
int n,m,num,A,B,wa,wb,cnt,ans;
int head[maxn],in[maxn];
int a[maxn],f[maxn][maxk];
struct edge{
    int to,nxt;
}e[maxm];
inline void add(int u,int v){
    ++in[v];
    e[++cnt]={v,head[u]};
    head[u]=cnt;
}
inline void topo(){
    memset(f,-0x3f,sizeof f);
    queue<int> q;q.push(1);f[1][0]=a[1];
    while(!q.empty()){
        int u=q.front();q.pop();
        for(re int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(!(--in[v])) q.push(v);
            for(re int j=B;j>1;--j) f[v][j-1]=max(f[v][j-1],f[u][j]);
            f[v][0]=max(f[v][0],f[u][1]+a[v]);
            if(A!=1) f[v][A-1]=max(f[v][A-1],f[u][0]-wa);
            else f[v][0]=max(f[v][0],f[u][0]-wa+a[v]);
            if(B!=1) f[v][B-1]=max(f[v][B-1],f[u][0]-wb);
            else f[v][0]=max(f[v][0],f[u][0]-wb+a[v]);
        }
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>num>>n>>m>>A>>B>>wa>>wb;
    for(re int i=1,pos,val;i<=num;++i) cin>>pos>>val,a[pos]+=val;
    for(re int i=1,u,v;i<=m;++i) cin>>u>>v,add(u,v);
    topo();
    int ans=0;
    for(re int i=1;i<=n;++i) ans=max(ans,f[i][0]);
    cout<<ans;
    return 0;
}

不可思议的迷宫

一开始看到期望还以为是困难题，结果是经典拆贡献分讨题。

不知道题解是怎么分的，感觉我分的似乎有点麻烦？不过懒得合并了。

以下内容省略了很多过程，直接给出了结果，大家可以思考一下是怎么得到的。

首先期望是假的，我们只需要算出距离和然后除以总方案数即可。

我们可以把一颗基环树画成这样：

我们把环上点记作 $rt_i$，其环外子树大小记作 $siz_i$，下文的子树都指环外子树。

显然，对于点对 $(u,v)$，若它们之间的路径经过了环上点，那么就一定会有两条路径，否则只有一条路径。

对于经过环上点的点对 $(u,v)$，可以发现它们的贡献可以拆成两部分：

1.环长的一半

2.$dis(rt_u,u)+dis(rt_v,v)$

对于不经过环上点的点对 $(u,v)$，它们只有距离贡献，没有环贡献。

所以我们对点对 $(u,v)$ 是否经过环上点分类讨论。

1. 不经过环上点

容易发现，这两个点一定都在同一颗子树内，且不经过根节点。

那么答案就为

$$\sum_{u \neq rt} \sum_{v\neq rt} dis(u,v)$$

差分一下，变为

$$\sum_{u} \sum_{v} dis(u,v)-\sum_{u} dis(rt,u)$$

前面这个东西是经典问题，考虑每条边的贡献即可。

因为点对是有序的，所以答案要 ×2。

1. 经过环上点

我们先计算环贡献。

这里我又拆成了三部分：子树内（不包括根）经过根节点的贡献，子树（不包括根）与外部点的贡献以及所有环上点的贡献。

设 $u$ 为根的儿子，环长的一半为 $len$，则第一部分答案为

$$\sum ((siz_{rt}-1)-siz_u)\times siz_u \times len$$

第二部分答案为

$$\sum (siz_{rt}-1)\times (n-(siz_{rt}-1))\times len$$

第三部分答案为

$$\sum n\times len$$

然后计算距离贡献。

对于点对 $(u,v)$，我们需要计算 $dis(rt_u,u)+dis(rt_v,v)$。

容易发现，点 $u$ 会和所有子树（不包括根）外的点产生这部分贡献，所以点 $u$ 的贡献为

$$dis(rt_u,u)\times (n-(siz_{rt}-1))$$

所以总贡献为

$$(n-(siz_{rt}-1))\times \sum_{rt} \sum_u dis_{rt,u}$$

因为点对是有序的，所以这部分贡献要 ×2。

感觉我的代码极其丑陋···

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=3e5+10,mod=19260817,inv2=9630409;
int n,cnt=1;
int ans,sum,rt,num;
int head[maxn],dis[maxn],siz[maxn];
struct edge{
    int to,nxt,w;
}e[maxn<<1];
inline int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
inline int Inv(int x){return qpow(x,mod-2);}
inline void add(int u,int v,int w){
    e[++cnt]={v,head[u],w};
    head[u]=cnt;
}
int tim;
int dfn[maxn],lst[maxn];
bitset<maxn> vis;
inline void get(int u,int v){vis[u]=1;while(v!=u) vis[v]=1,v=e[lst[v]^1].to;}
inline void dfs(int u){
    dfn[u]=++tim;
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]) lst[v]=i,dfs(v);
        else if(i^1!=lst[u]&&dfn[v]>dfn[u]) get(u,v);
    }
}
inline void dfs1(int u,int fa){
    sum+=dis[u];siz[u]=1;
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa||vis[v]) continue;
        dis[v]=dis[u]+e[i].w;
        dfs1(v,u);
        siz[u]+=siz[v];
    }
}
inline void dfs2(int u,int fa){
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa||vis[v]) continue;
        ans=(ans+2*e[i].w%mod*siz[v]%mod*(siz[rt]-siz[v])%mod)%mod;
        dfs2(v,u);
    }
}
bool flag;
inline void dfs3(int u,int fa){
    if(u==rt&&sum){flag=1;return;}
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa||!vis[v]) continue;
        sum+=e[i].w;
        dfs3(v,u);
        if(flag) return;
    }
}
inline void dfs4(int u,int fa){
    if(fa==rt) ans=(ans+(siz[rt]-1-siz[u])*siz[u]*sum%mod)%mod;
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa||vis[v]) continue;
        dfs4(v,u);
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(re int i=1,u,v,w;i<=n;++i) cin>>u>>v>>w,add(u,v,w),add(v,u,w);
    dfs(1);
    for(re int i=1;i<=n;++i){
        if(vis[i]){
            sum=0;rt=i;
            dfs1(rt,0);dfs2(rt,0);
            ans=((ans-sum*2)%mod+mod)%mod;
            ans=(ans+2*(n-(siz[rt]-1))*sum%mod)%mod;
        }
    }
    for(re int i=1;i<=n;++i){
        if(vis[i]){
            sum=0;rt=i;
            dfs3(i,0);
            sum=sum*inv2%mod;
            break;
        }
    }
    for(re int i=1;i<=n;++i){
        if(vis[i]){
            rt=i;
            dfs4(i,0);
            ans=(ans+(siz[i]-1)%mod*(n-(siz[i]-1))%mod*sum)%mod;
            ans=(ans+n*sum%mod)%mod;
        }
    }
    cout<<ans*Inv(n*n%mod)%mod;
    return 0;
}

「Wdsr-1」笨蛋结构

原来是套路题吗？感觉没怎么见过啊，看来要加训了。

关于区间加多项式

设区间加的范围为 $[l,r]$，$l\le i \le r$。

根据二项式定理，$w\times (i-l+1)^k=w\sum_{j=0}^k \binom{k}{j}i^j(1-l)^{k-j}$。

对于每个位置 $i$，我们将其视为维护了一个 $x=i$ 的 $k$ 次多项式。

那么区间加操作相当于对 $[l,r]$ 里的每个多项式都加上 $w\sum_{j=0}^k \binom{k}{j}i^j(1-l)^{k-j}$。

因为每一项都加的一样，所以区间加被转化为了做 $k$ 次区间加。

因为没有边问边查，所以可以差分维护。

复杂度 $O(qm+nm)$

#include"bits/stdc++.h"
#define re register
// #define int long long
using namespace std;
typedef unsigned long long u64;
typedef unsigned int       u32;
u32 MT[624],idx;
void _init(u32 seed){
    MT[0]=seed; idx=0; for(int i=1;i<624;++i) 
    MT[i]=(0x6c078965*(MT[i-1]^((MT[i-1])>>30)+i));
}
void _gene(){
    for(int i=0;i<624;++i){
        int x=MT[i]&0x80000000+(MT[(i+1)%624]&0x7fffffff);
        MT[i]=MT[(i+397)%624]^(x>>1);
        if(x&2)MT[i]^=0x9908b0df;
    }
}
u32  _calc(){
    if(!idx) _gene(); int x=MT[idx];
    x^=x>>11,x^=(x<<7)&(0x9d2c5680);
    x^=(x<<15)&0xefc60000,x^=x>>18;
    idx=(idx+1)%624; return x;
}
u64 _get(){u64 ret=_calc()*_calc(); return ret;}
u64 _get(u64 _l,u64 _r){return _get()%(_r-_l+1ull)+_l;}
void input(int &_n,int &_m,int &_q,int *_S,int *_L,u64 *_W,int *_K){
    u32 seed; scanf("%d%d%d%u",&_n,&_m,&_q,&seed); _init(seed); int i=1;
    if(_n>100) for(;i<=_q/4;++i){
        int _a=_get(1,_n-100),_b=_get(_a+_m,_a+_m+1),_l=_b-_a+1,_k=_get(0,_m);
        u64 _w=_get(); _S[i]=_a,_L[i]=_l,_W[i]=_w,_K[i]=_k;
    }
    if(_n>100) for(;i<=_q/2;++i){
        int _a=_get(1,100),_b=_get(_n-100,_n),_l=_b-_a+1,_k=_get(0,_m);
        u64 _w=_get(); _S[i]=_a,_L[i]=_l,_W[i]=_w,_K[i]=_k;
    }
    for(;i<=_q;++i){
        int _a=_get(1,_n),_b=_get(1,_n); if(_a>_b) swap(_a,_b);
        int _l=_b-_a+1,_k=_get(0,_m); u64 _w=_get();
        _S[i]=_a,_L[i]=_l,_W[i]=_w,_K[i]=_k;
    }
}
void output(int n,u64 *R){
    u64 ret=n^_get(); for(int i=1;i<=n;i++) ret^=_get()+R[i];
    printf("%llu\n",ret);
}
const int maxn=5e5+10,maxq=1e6+10,maxm=10;
int n,m,q;
u64 C[maxm][maxm],a[maxn][maxm],ans[maxn],w[maxq];
int s[maxq],len[maxq],k[maxq];
inline void init(){
    C[0][0]=1;
    for(re int i=1;i<=m;++i){
        C[i][0]=1;
        for(re int j=1;j<=i;++j) C[i][j]=C[i-1][j]+C[i-1][j-1];
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    input(n,m,q,s,len,w,k);
    init();
    for(re int i=1;i<=q;++i){
        u64 tmp=w[i];
        for(re int j=k[i];~j;--j){
            a[s[i]][j]+=tmp*C[k[i]][j];
            a[s[i]+len[i]][j]-=tmp*C[k[i]][j];
            tmp*=(1-s[i]);
        }
    }
    for(re int i=1;i<=n;++i){
        u64 tmp=1;
        for(re int j=0;j<=m;++j){
            a[i][j]+=a[i-1][j];
            ans[i]+=tmp*a[i][j];
            tmp*=i;
        }
    }
    output(n,ans);
    return 0;
}

「Wdsr-1」人间之里

第一眼想到了[SCOI2014] 方伯伯的商场之旅？

如果我们知道了选哪个位置当作避难所，那么答案和修改是很好做的，拆一下绝对值然后就可以线段树轻松维护了。

那么关键问题是：如何选避难所？

可以感性的得到一个结论：一定要选到有人的点上。

首先想到了二分，然后想到了带权中位数。

二分没想明白单调性，带权中位数也没太想明白。

然后就没想出来。

下面仔细说一下单调性。

设避难所位置为 $p$，$sum=\sum_{i=l}^r a_i,suml=\sum_{i=l}^p a_i,sumr=\sum_{i=p+1}^r a_i$。

结论：最优的 $p$ 一定要使 $suml$ 和 $sumr$ 尽可能接近 $\frac {sum}{2}$。

证明：

假设当前的 $p$ 满足 $suml > sumr$。

那么当 $p$ 变为 $p+1$ 时，答案的增量为 $suml-sumr$。

这显然会让答案更劣，所以我们不会让 $p$ 变为 $p+1$。

经过这样的操作，我们会发现 $suml$ 和 $sumr$ 都在接近 $\frac {sum}{2}$。

所以可以二分找到这个 $p$。

二分+线段树是两个 $\log$，改为线段树上二分就是一个 $\log$。

注意：最终二分到的位置可能不是最优解，需要再求一下 $p-1$ 和 $p+1$。

这是不是就是带权中位数啊？

帕秋莉的魔导书

这是紫？这是紫？这是紫？

容易发现答案是前缀和区间求和然后除以区间长度。

所以维护线段树维护前缀和即可。

「Wdsr-1」仓库建设

一个点 $u$ 可以到达的点 $v$，需要满足存在 $u$ 到 $v$ 的一条路径，使得边权最大值 $\le$ $u$ 的点权。

容易想到 Kruskal 重构树。

设点 $u$ 向上倍增找到的最浅点为 $p_u$，$p_u$ 能覆盖到的叶子区间为 $[l,r]$。

那么现在问题转化为了：

给定若干线段，求完全覆盖区间 $[1,n]$ 的最小线段数。

这是经典贪心，排序后双指针即可。

然后现在还要求：

每次删除一条线段，求删除该线段后的最小线段数。

可以发现，只有删除的线段在最优解里用过且只有一条和它一模一样的线段时，答案才可能发生变化，所以只需要考虑这种情况。

因为我们是从树上转化来的线段，所以可以保证线段要么包含要么不交。

那么把这条线段删除以后，我们只需要看被它包含的线段能不能把它补上。

假设第一条是要被删的线段，那么我们只需要考虑第二层这些线段，而不用考虑第二层以下的线段（即被第二层线段完全包含的那些线段）。

所以可以预处理出：如果这条线段被删掉，用来补充的第二层线段有哪些。

每条线段最多被遍历一次，所以这部分复杂度为 $O(n)$。

事实上，上面说的这一堆和题解说的在重构树上 dfs 是完全一致的，只不过我把它抽象成了线段。

而且这样做写起来也挺难写的（因为我不会写双指针），所以理解一下意思就行了。

不过这种把树上问题转化为区间问题的思路还是挺有启发意义的？

「Wdoi-1」托卡马克

贪心只能纯靠猜，不过这次猜对了。

对于求最大值，不难想到排序后，选最左侧和最右侧的各 $\frac {m}{2}$ 个点就是最优的。

证明可以考虑反证法：把其中的一个点换成一个靠中间的点一定不优，显然让答案变小了。

那么怎么求次大值呢？

经过手玩样例和打表，发现：把第 $\frac {m}{2}$ 个点（即最左侧点中最靠右的那个）换成它右边那个或把第 $\frac {m}{2}+1$ 个点（即最右侧点中最靠左的那个）换成它左边那个就是次大。

然后交上去，发现错了。

事实上，我们换到的新点的值可能和原来一样，这时答案不变。

所以结论应该是：把第 $\frac {m}{2}$ 个点（即最左侧点中最靠右的那个）换成它右边第一个和它不同的点或把第 $\frac {m}{2}+1$ 个点（即最右侧点中最靠左的那个）换成它左边第一个和它不同的点就是次大。

当然，有可能找不到不一样的点，那就换成左侧/右侧的继续找就行了。

注意判无解。

[Cnoi2019] 雪松果树

加强版：「TOCO Round 1」History

对于维护 $k$ 级表亲信息的题目，通常可以用一种 bfs 序+dfs 序的方式维护。

我们对每个深度维护出它对应的 bfs 序，然后把 bfs序对应到 dfs序上。

设要求点 $u$ 的 $k$ 级表亲信息，那么我们先求出来 $u$ 的 $k$ 级祖先 $fa$，然后在 $u$ 所在深度对应的 bfs序区间上，二分找出 dfs序在 $fa$ 的子树对应的区间里的一段区间。

这段区间就是 $u$ 的 $k$ 级表亲（包括 $u$）。

所以我们维护的信息要在 bfs序上维护。

感觉说的有点抽象，具体可以看代码，应该还是挺好懂的。

#include"bits/stdc++.h"
#define re register
// #define int long long
using namespace std;
const int maxn=1e6+10;
int n,q,cnt,tim;
int head[maxn],fa[maxn][21],seq[maxn];
struct edge{
    int to,nxt;
}e[maxn];
struct node{
    int l,r,dep,bfn;
}t[maxn];
struct line{
    int l,r;
}Dep[maxn];
struct BIT{
    int tr[maxn];
    #define lb(x) (x&(-x))
    inline void add(int x,int val){while(x<=n) tr[x]+=val,x+=lb(x);}
    inline int query(int x){int res=0;while(x) res+=tr[x],x-=lb(x);return res;}
    #undef lb(x)
}a;
inline void add(int u,int v){
    e[++cnt]={v,head[u]};
    head[u]=cnt;
}
inline void bfs(int s){
    queue<int> q;
    q.push(s);t[s].dep=1,Dep[1].l=++tim,t[s].bfn=tim;
    while(!q.empty()){
        int u=q.front();q.pop();
        Dep[t[u].dep].r=t[u].bfn;
        for(re int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            t[v].dep=t[u].dep+1;
            t[v].bfn=++tim;
            if(!Dep[t[v].dep].l) Dep[t[v].dep].l=tim;
            q.push(v);
        }
    }
}
inline void dfs(int u){
    t[u].l=++tim;seq[t[u].bfn]=tim;a.add(t[u].bfn,1);
    for(re int j=1;j<=20;++j) fa[u][j]=fa[fa[u][j-1]][j-1];
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        dfs(v);
    }
    t[u].r=tim;
}
inline int find(int u,int dep){
    for(re int i=20;i>=0;--i) if(dep>=(1<<i)) u=fa[u][i],dep-=(1<<i);
    return u;
}
inline int solve(int u,int k){
    int f=find(u,k);
    if(!f) return 0;
    int l=Dep[t[u].dep].l,r=Dep[t[u].dep].r,mid,L=t[f].l,R=t[f].r;
    while(l<=r){
        mid=(l+r)>>1;
        if(seq[mid]>=t[f].l) L=mid,r=mid-1;
        else l=mid+1;
    }
    l=Dep[t[u].dep].l,r=Dep[t[u].dep].r;
    while(l<=r){
        mid=(l+r)>>1;
        if(seq[mid]<=t[f].r) R=mid,l=mid+1;
        else r=mid-1;
    }
    return a.query(R)-a.query(L-1)-1;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(re int v=2,u;v<=n;++v) cin>>u,add(u,v),fa[v][0]=u;
    bfs(1);tim=0;dfs(1);
    for(re int i=1,u,k;i<=q;++i) cin>>u>>k,cout<<solve(u,k)<<' ';
    return 0;
}

连环病原体

想出来了，但现在不会写 LCT 了（悲）。

容易发现，若 $[l,r]$ 有环，则所有包含 $[l,r]$ 的区间都必定有环。

所以我们只需要对于每个 $l$，求出第一个使得 $[l,r]$ 有环的 $r$ 即可。

可以发现，$r$ 关于 $l$ 单调不降，所以可以双指针。

维护连通性用 LCT 即可。

然后是怎么算贡献。

对于一个有环区间 $[l,r]$，它会贡献到 $[l,r],[l,r+1]\cdots [l,n]$。

所以对于每个 $l$，都有 $O(n)$ 次区间加，差分以后变成 $O(n)$ 次单点加。

可以发现，差分以后是对 $l$ 加上 $n-r+1$，对 $[r+1,n+1]$ 区间减 1。

后面这个可以再差分一下，不过无所谓了，反正只有 $O(n)$ 次区间减，多带个 $\log$ 应该也没啥。

LCT 是从模板贺的。

#include"bits/stdc++.h"
#define re register
#define int long long
#define ls(x) tr[x].ch[0]
#define rs(x) tr[x].ch[1]
#define fa(x) tr[x].fa
#define get(x) (rs(fa(x))==x)
#define isroot(x) (ls(fa(x))!=x&&rs(fa(x))!=x)
using namespace std;
const int maxn=2e5+10;
int n;
int a[maxn];
int s1[maxn],s2[maxn];
struct edge{
    int u,v;
}e[maxn];
struct node{
    int fa,ch[2],tag;
}tr[maxn];
inline void rev(int x){swap(ls(x),rs(x));tr[x].tag^=1;}
inline void down(int x){if(tr[x].tag){rev(ls(x)),rev(rs(x)),tr[x].tag=0;}}
inline void update(int x){if(!isroot(x)){update(fa(x));}down(x);}
inline void rotate(int x){
    int y=fa(x),z=fa(y),t=get(x);
    if(!isroot(y)) tr[z].ch[get(y)]=x;
    fa(tr[x].ch[t^1])=y,tr[y].ch[t]=tr[x].ch[t^1];
    tr[x].ch[t^1]=y;
    fa(y)=x,fa(x)=z;
}
inline void splay(int x){
    update(x);
    for(re int f=fa(x);f=fa(x),!isroot(x);rotate(x)){
        if(!isroot(f)) rotate(get(f)==get(x)?f:x);
    }
}
inline void access(int x){for(re int p=0;x;p=x,x=fa(x)){splay(x),rs(x)=p;}}
inline void makeroot(int x){access(x),splay(x),rev(x);}
inline int find(int x){
    access(x),splay(x);
    while(ls(x)) x=ls(x),down(x);
    splay(x);
    return x;
}
inline void split(int x,int y){makeroot(x),access(y),splay(y);}
inline void link(int x,int y){makeroot(x);if(find(y)!=x) fa(x)=y;}
inline void cut(int x,int y){makeroot(x);if(find(y)==x&&fa(y)==x&&!ls(y)) fa(y)=rs(x)=0;}
inline void add(int l,int r){s1[l]+=(n-r+1);s1[r+1]-=(n-r+1);++s2[r+1];}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(re int i=1;i<=n;++i) cin>>e[i].u>>e[i].v;
    int now=1;
    for(re int i=1;i<=n;++i){
        while(find(e[i].u)==find(e[i].v)){
            add(now,i);
            cut(e[now].u,e[now].v);
            ++now;
        }
        link(e[i].u,e[i].v);
    }
    for(re int i=1;i<=n;++i){
        s1[i]+=s1[i-1];s2[i]+=s2[i-1];
        cout<<s1[i]+(n-i+1)*s2[i]<<' ';
    }
    return 0;
}

帕秋莉的魔法

没有样例解释，且题意不明，被硬控 0.5h。

说一下坑点：

1. 如果现在选了 $i$，那么只有下一个选的 $j$ 能受到 $w_{i,j}$ 的加成。
2. 物品体积可能为负。
3. 要求的是选体积和恰好为 $m$ 的物品。

弄明白题以后，状态和转移都是好想的，就一个背包变形。

设 $f_{i,j}$ 表示前 $i$ 个选了体积恰好为 $j$ 的物品，转移为

$$f_{i,j}=\max_{k<i} f_{k,j-a_i}+b_i+w_{k,i}$$

因为有负数，所以要加一个偏移量。

Marisa采蘑菇

弱化版：[HEOI2012] 采花

弱弱化版：[SDOI2009] HH的项链

第一眼以为是莫队简单题，结果一看数据范围···

结果我发现我连HH的项链都不会做，所以我们从最简单的这道题入手。

二维数点做法和莫队做法不再赘述，因为它们都解决不了我们的加强版。

对于一种颜色，我们考虑在最后一次出现时算它的贡献。

我们将询问离线，按右端点升序排序，然后维护一个指针从左向右扫。

我们对每种颜色维护它上一次出现的位置。

当扫到一种出现过的颜色时，我们把上一次出现的位置的贡献减去，然后加到当前位置，然后更新上一次出现的位置。

把当前询问扫完以后，我们直接区间求和即可。

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e6+10;
int n,m;
int a[maxn],lst[maxn],ans[maxn];
struct query{
    int l,r,id;
    inline bool operator < (const query &a)const{return r<a.r;}
}q[maxn];
struct BIT{
    int tr[maxn];
    #define lb(x) (x&(-x))
    inline void add(int x,int val){while(x<=n) tr[x]+=val,x+=lb(x);}
    inline int query(int x){int res=0;while(x) res+=tr[x],x-=lb(x);return res;}
    inline int query(int l,int r){return query(r)-query(l-1);}
    #undef lb(x)
}b;
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(re int i=1;i<=n;++i) cin>>a[i];
    cin>>m;
    for(re int i=1;i<=m;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+m+1);
    int pos=1;
    for(re int i=1;i<=m;++i){
        for(re int j=pos;j<=q[i].r;++j){
            if(lst[a[j]]) b.add(lst[a[j]],-1);
            b.add(j,1);
            lst[a[j]]=j;
        }
        pos=q[i].r+1;
        ans[q[i].id]=b.query(q[i].l,q[i].r);
    }
    for(re int i=1;i<=m;++i) cout<<ans[i]<<'\n';
    return 0;
}

然后来看弱化版。

对于一种颜色，我们考虑在倒数第二次出现时算它的贡献。

我们将询问离线，按右端点升序排序，然后维护一个指针从左向右扫。

我们对每种颜色维护它上一次出现的位置和上上次出现的位置。

当扫到一种出现过的颜色时，我们把上上次出现的位置的贡献减去，然后加到上一次出现的位置，然后更新上一次出现的位置和上上次出现的位置。

代码基本一样。

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=2e6+10;
int n,m,c;
int a[maxn],lst1[maxn],lst2[maxn],ans[maxn];
struct query{
    int l,r,id;
    inline bool operator < (const query &a)const{return r<a.r;}
}q[maxn];
struct BIT{
    int tr[maxn];
    #define lb(x) (x&(-x))
    inline void add(int x,int val){while(x<=n) tr[x]+=val,x+=lb(x);}
    inline int query(int x){int res=0;while(x) res+=tr[x],x-=lb(x);return res;}
    inline int query(int l,int r){return query(r)-query(l-1);}
    #undef lb(x)
}b;
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>c>>m;
    for(re int i=1;i<=n;++i) cin>>a[i];
    for(re int i=1;i<=m;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+m+1);
    int pos=1;
    for(re int i=1;i<=m;++i){
        for(re int j=pos;j<=q[i].r;++j){
            if(!lst1[a[j]]) lst1[a[j]]=j;
            else if(!lst2[a[j]]){
                b.add(lst1[a[j]],1);
                lst2[a[j]]=j;
            }
            else{
                b.add(lst1[a[j]],-1),b.add(lst2[a[j]],1);
                lst1[a[j]]=lst2[a[j]],lst2[a[j]]=j;
            }
        }
        pos=q[i].r+1;
        ans[q[i].id]=b.query(q[i].l,q[i].r);
    }
    for(re int i=1;i<=m;++i) cout<<ans[i]<<'\n';
    return 0;
}

所以根据这个套路，我们对于维护出现次数 $\ge x$ 的颜色的个数的问题，依旧可以这么做：

1. 对于一种颜色，我们考虑在倒数第 $x$ 次出现时算它的贡献。
2. 我们将询问离线，按右端点升序排序，然后维护一个指针从左向右扫。
3. 我们对每种颜色维护它上一次出现的位置，上上次出现的位置···上 $x$ 次出现的位置。
4. 当扫到一种出现过的颜色时，我们把上 $x$ 次出现的位置的贡献减去，然后加到上 $x-1$ 次出现的位置，然后更新上一次出现的位置，上上次出现的位置···上 $x$ 次出现的位置。

那么现在来看这道加强版。

设区间 $[l,r]$ 内颜色 $c$ 出现次数为 $x$，出现总次数为 $sum$，则该颜色能产生贡献当且仅当

$$|x-(sum-x)|\le k$$

把绝对值拆一下，可以得到

$$\max (1,\lceil \frac {sum-k}{2} \rceil) \le x \le \lfloor \frac {sum+k}{2} \rfloor$$

所以问题转化为：求 $\sum_{i=l}^r [l_{c_i} \le num_{c_i} \le r_{c_i}]$。

如果所有颜色的范围限制都一样，那还好做，用出现次数 $\ge l$ 的减去 $\ge r+1$ 的即可。

但是现在范围不一样，再直接套用之前算贡献的方法似乎不能做。

所以我们现在这样算贡献：对于颜色 $c_i$，我们在出现次数为 $l_i$ 的地方 +1，在出现次数为 $r_i+1$ 的地方 -1，这样求前缀和得到的就是正确贡献。

我们将询问离线，按左端点升序排序，然后维护一个指针从左向右扫。

对于当前询问区间 $[l,r]$，我们让指针扫到 $l-1$ 时停止。

对于扫到的颜色，我们让它出现次数为 $l_i$ 的地方向后跳一个，出现次数为 $r_i+1$ 的地方也向后跳一个。

那么这个询问的答案就是右端点求个前缀和。

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e6+10;
int n,m,k;
int a[maxn],lst[maxn],nxt[maxn],ans[maxn];
int lc[maxn],rc[maxn];
int buc[maxn];
bitset<maxn> vis;
struct query{
    int l,r,id;
    inline bool operator < (const query &a)const{return l<a.l;}
}q[maxn];
struct node{
    int l,r;
}t[maxn];
struct BIT{
    int tr[maxn];
    #define lb(x) (x&(-x))
    inline void add(int x,int val){while(x<=n) tr[x]+=val,x+=lb(x);}
    inline int query(int x){int res=0;while(x) res+=tr[x],x-=lb(x);return res;}
    #undef lb(x)
}b;
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for(re int i=1;i<=n;++i) cin>>a[i],++buc[a[i]],lst[a[i]]=n+1;nxt[n+1]=n+1;
    for(re int i=1;i<=n;++i) t[a[i]].l=max(1ll,(buc[a[i]]-k+1)>>1),t[a[i]].r=(buc[a[i]]+k)>>1;
    for(re int i=n;i>=1;--i) nxt[i]=lst[a[i]],lst[a[i]]=i;
    for(re int i=1,res;i<=n;++i){
        if(!vis[a[i]]){
            vis[a[i]]=1;lc[a[i]]=rc[a[i]]=i;
            res=1;while(res<t[a[i]].l&&lc[a[i]]^(n+1)) ++res,lc[a[i]]=nxt[lc[a[i]]];b.add(lc[a[i]],1);
            res=0;while(res<t[a[i]].r&&rc[a[i]]^(n+1)) ++res,rc[a[i]]=nxt[rc[a[i]]];b.add(rc[a[i]],-1);
        }
    }
    for(re int i=1;i<=m;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+m+1);
    int pos=1;
    for(re int i=1;i<=m;++i){
        for(re int j=pos;j<q[i].l;++j){
            b.add(lc[a[j]],-1),b.add(rc[a[j]],1);
            lc[a[j]]=nxt[lc[a[j]]],rc[a[j]]=nxt[rc[a[j]]];
            b.add(lc[a[j]],1),b.add(rc[a[j]],-1);
        }
        pos=q[i].l;
        ans[q[i].id]=b.query(q[i].r);
    }
    for(re int i=1;i<=m;++i) cout<<ans[i]<<'\n';
    return 0;
}

哦，那好像这个加强版才是通法。

我们对于维护出现次数在 $[l_i,r_i]$ 的颜色的个数的问题，可以这么做：

1. 对于一种颜色，我们考虑在第 $l_i$ 次出现时加上它的贡献，在第 $r_i+1$ 次出现时减去贡献。
2. 我们将询问离线，按左端点升序排序，然后维护一个指针从左向右扫。
3. 我们对每种颜色维护它当前位置下一个这种颜色的位置。
4. 当扫到一种出现过的颜色时，我们把 +1 的贡献和 -1 的贡献都往后跳一个。
5. 答案为查询区间右端点做前缀和。

HH的项链 代码：

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e6+10;
int n,m,k;
int a[maxn],lst[maxn],nxt[maxn],ans[maxn];
int lc[maxn];
bitset<maxn> vis;
struct query{
    int l,r,id;
    inline bool operator < (const query &a)const{return l<a.l;}
}q[maxn];
struct node{
    int l,r;
}t[maxn];
struct BIT{
    int tr[maxn];
    #define lb(x) (x&(-x))
    inline void add(int x,int val){while(x<=n) tr[x]+=val,x+=lb(x);}
    inline int query(int x){int res=0;while(x) res+=tr[x],x-=lb(x);return res;}
    #undef lb(x)
}b;
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(re int i=1;i<=n;++i) cin>>a[i],lst[a[i]]=n+1;nxt[n+1]=n+1;
    for(re int i=n;i>=1;--i) nxt[i]=lst[a[i]],lst[a[i]]=i;
    for(re int i=1;i<=n;++i){
        if(!vis[a[i]]){
            vis[a[i]]=1;
            lc[a[i]]=i;b.add(lc[a[i]],1);
        }
    }
    cin>>m;
    for(re int i=1;i<=m;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+m+1);
    int pos=1;
    for(re int i=1;i<=m;++i){
        for(re int j=pos;j<q[i].l;++j){
            b.add(lc[a[j]],-1);
            lc[a[j]]=nxt[lc[a[j]]];
            b.add(lc[a[j]],1);
        }
        pos=q[i].l;
        ans[q[i].id]=b.query(q[i].r);
    }
    for(re int i=1;i<=m;++i) cout<<ans[i]<<'\n';
    return 0;
}

采花 代码：

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=2e6+10;
int n,m,c;
int a[maxn],lst[maxn],nxt[maxn],ans[maxn];
int lc[maxn];
bitset<maxn> vis;
struct query{
    int l,r,id;
    inline bool operator < (const query &a)const{return l<a.l;}
}q[maxn];
struct node{
    int l,r;
}t[maxn];
struct BIT{
    int tr[maxn];
    #define lb(x) (x&(-x))
    inline void add(int x,int val){while(x<=n) tr[x]+=val,x+=lb(x);}
    inline int query(int x){int res=0;while(x) res+=tr[x],x-=lb(x);return res;}
    #undef lb(x)
}b;
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>c>>m;
    for(re int i=1;i<=n;++i) cin>>a[i],lst[a[i]]=n+1;nxt[n+1]=n+1;
    for(re int i=n;i>=1;--i) nxt[i]=lst[a[i]],lst[a[i]]=i;
    for(re int i=1;i<=n;++i){
        if(!vis[a[i]]){
            vis[a[i]]=1;
            lc[a[i]]=nxt[i];
            b.add(lc[a[i]],1);
        }
    }
    for(re int i=1;i<=m;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+m+1);
    int pos=1;
    for(re int i=1;i<=m;++i){
        for(re int j=pos;j<q[i].l;++j){
            b.add(lc[a[j]],-1);
            lc[a[j]]=nxt[lc[a[j]]];
            b.add(lc[a[j]],1);
        }
        pos=q[i].l;
        ans[q[i].id]=b.query(q[i].r);
    }
    for(re int i=1;i<=m;++i) cout<<ans[i]<<'\n';
    return 0;
}

天守阁的地板

双倍经验：Product

题意：求

$$\prod_{i=1}^n\prod_{j=1}^n \frac {\operatorname{lcm}(i,j)}{\gcd(i,j)}$$

先拆 $\operatorname{lcm}$，得到

$$\prod_{i=1}^n\prod_{j=1}^n \frac {i\times j}{\gcd(i,j)^2}$$

分子分母分开看，上面很好算。

$$\begin{align*} \prod_{i=1}^n\prod_{j=1}^n i\times j &=(\prod_{i=1}^ni)^n\times (\prod_{j=1}^n j)^n \\ &=n!^n\times n!^n \\ &= n!^{2n} \end{align*}$$

然后算分母。

$$\prod_{i=1}^n\prod_{j=1}^n \gcd(i,j)$$

套路的枚举 $\gcd$。

$$\prod_{i=1}^n\prod_{j=1}^n \gcd(i,j)=\prod_{d=1}^n d^{\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=d]}$$

指数部分太熟了，直接莫反。

$$\begin{align*} \sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=d]&=\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor}[\gcd(i,j)=1] \\ &=\sum_{p=1}^{\lfloor \frac{n}{d}\rfloor} \mu (p)\times \lfloor \frac{n}{dp}\rfloor^2 \end{align*}$$

设 $f(n)=\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]$，则

$$\prod_{d=1}^n d^{\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=d]}=\prod_{d=1}^n d^{f(\lfloor \frac{n}{d}\rfloor)}$$

可以两次数论分块，复杂度 $O(T\times n^{\frac {3}{4}})$。

不过复杂度有点劣，能不能再优些？

再看一遍式子：

$$\prod_{d=1}^n d^{\sum_{p=1}^{\lfloor \frac{n}{d}\rfloor} \mu (p)\times \lfloor \frac{n}{dp}\rfloor^2}$$

看到枚举的变量乘在一起了，套路的枚举乘积，则

$$\prod_{d=1}^n d^{\sum_{p=1}^{\lfloor \frac{n}{d}\rfloor} \mu (p)\times \lfloor \frac{n}{dp}\rfloor^2}=\prod_{t=1}^n (\prod_{d|t}d^{\mu(\frac {t}{d})})^{\lfloor \frac{n}{t}\rfloor^2}$$

里面这东西显然可以枚举倍数预处理，外层可以整除分块。

复杂度 $O(n\log n+T\sqrt n\log n)$。

整除分块里的 $\log$ 是快速幂。

双倍经验被卡空间了，大家还是写欧拉反演吧。

upd：补一下欧拉反演的做法。

从这一步开始

$$\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor}[\gcd(i,j)=1]$$

刚才的处理是莫反，这次试试欧拉反演。

因为

$$\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^i[\gcd(i,j)=1]=\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\varphi(i)$$

所以

$$\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor}[\gcd(i,j)=1]=2\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\varphi(i)-1$$

然后代回去

$$\frac {n!^{2n}}{(\prod_{d=1}^n d^{2\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\varphi(i)-1})^2}$$

把指数整理一下

$$\frac {n!^{2n+2}}{(\prod_{d=1}^n d^{\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\varphi(i)})^4}$$

处理个 $\varphi$ 的前缀和就没了。

复杂度 $O(n+T\sqrt n)$

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e6+10,V=1e6,mod=19260817;
int n,cnt;
int pri[maxn],mu[maxn];
int inv[maxn];
int a[maxn],prod[maxn];
int fac[maxn],inv1[maxn],Inv1[maxn];
int Fac[maxn];
bitset<maxn> vis;
inline int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
inline int Inv(int x){return qpow(x,mod-2);}
inline void sieve(){
    mu[1]=1;
    for(re int i=2;i<=V;++i){
        if(!vis[i]) pri[++cnt]=i,mu[i]=-1;
        for(re int j=1;j<=cnt&&i*pri[j]<=V;++j){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0) break;
            else mu[i*pri[j]]=-mu[i];
        }
    }
}
inline void init(){
    inv[0]=inv[1]=1;
    for(re int i=2;i<=V;++i) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    for(re int i=1;i<=V;++i) a[i]=1;
    for(re int i=1;i<=V;++i){
        for(re int j=i;j<=V;j+=i){
            if(mu[j/i]==-1) a[j]=a[j]*inv[i]%mod;
            if(mu[j/i]==1) a[j]=a[j]*i%mod;
        }
    }
    prod[0]=1;
    for(re int i=1;i<=V;++i) prod[i]=prod[i-1]*a[i]%mod;
    fac[0]=inv1[0]=1;
    for(re int i=1;i<=V;++i) fac[i]=fac[i-1]*prod[i]%mod;
    Inv1[V]=Inv(fac[V]);
    for(re int i=V-1;i>=1;--i) Inv1[i]=Inv1[i+1]*prod[i+1]%mod;
    for(re int i=1;i<=V;++i) inv1[i]=fac[i-1]*Inv1[i]%mod;
    Fac[0]=1;
    for(re int i=1;i<=V;++i) Fac[i]=Fac[i-1]*i%mod;
}
inline void solve(){
    cin>>n;
    int ans=1;
    for(re int l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        int res=prod[r]*inv1[l-1]%mod;
        int p=n/l;
        res=qpow(res,p*p);
        ans=ans*res%mod;
    }
    cout<<qpow(Fac[n],2*n)%mod*Inv(ans*ans%mod)%mod<<'\n';
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    sieve();init();
    int T;cin>>T;while(T--) solve();
    return 0;
}

[CTSC2015] 日程管理

双倍经验：[ABC363G] Dynamic Scheduling

如果把这题弱化一下，那么这是道经典的反悔贪心。

例题：[USACO09OPEN] Work Scheduling G

现在带上了修改，我们考虑用数据结构维护贪心。

首先考虑：如果给定若干个任务必须完成，怎么判断有没有解？

对于一个时间 $t$，只要必须在 $t$ 之前完成的任务数量 $\le t$ 即可。

所以我们可以类似之前的一道题Koishi Loves Segments，用线段树维护这个东西。

那么在 $t$ 加入任务时，我们就给 $[t,n]$ 区间 -1。

现在考虑插入一个任务 $(t,p)$。

如果 $[t,n]$ 的最小值 $> 0$，那么显然可以直接把这个任务加进去。

否则，我们贪心的考虑：拿这个新任务换掉之前的一个价值较低的任务。

那么这个新任务能替换哪些旧任务呢？

我们找到 $[t,n]$ 中第一个值为 $0$ 的时刻 $t_1$，那么说明 $t_1$ 时刻及以前已经被占满了。

我们找到截止时间在 $[1,t_1]$ 内的价值最小的任务然后尝试替换。

到这里可能会有疑问：为什么是在 $[1,t_1]$ 之间找最小的替换？新任务的截止时间不是 $t$ 吗？万一放进去不合法怎么办？

题目给的是任务的截止时间，而不是完成时间。也就是说，对于一个截止时间为 $t$ 的任务，我们只需要随便找一个 $[1,t]$ 的时刻分配给它即可。

那万一要是 $[1,t_1]$ 里的任务的截止时间都是 $t$ 怎么办？你这样不是放不进去了吗？

这显然不可能。

因为如果截止时间都是 $t$，那么你找到的 $t_1$ 就会等于 $t$，而不是 $t_1$。

所以说，在 $[1,t_1]$ 内，一定存在一种分配方案，使得你把旧任务删掉，然后把这个新任务插进去合法。

对于维护 $[1,t_1]$ 内的用过的价值最小的任务，可以再开一颗线段树。

然后考虑删除一个任务 $(t,p)$。

如果这个任务没在最优方案里，那就直接删掉。

否则，把这个任务删掉，然后我们贪心的考虑：拿一个价值最大的任务补上来。

那么哪些任务能补上来呢？

我们找到 $[1,n]$ 中最后一个值为 $0$ 的时刻 $t_1$（不存在则为 $0$），那么说明 $t_1$ 时刻及以前已经被占满了。

所以截止时间在 $[t_1+1,n]$ 内的没用过的任务都可以用。

我们选最大的那个加入即可。

对于维护 $[t_1+1,n]$ 内的没用过的价值最大的任务，可以再开一颗线段树。

因为任务的截止时间可能一样，所以后两颗线段树上要维护 multiset。

复杂度 $O(n\log^2 n)$。

代码看着长，但想清楚了并不难写。

#include"bits/stdc++.h"
#define re register
#define int long long
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
using namespace std;
const int maxn=3e5+10,inf=1e18;
int n,m,ans;
struct node1{
    int l,r,sum;
    inline node1 operator + (const node1 &a)const{
        if(sum==a.sum) return {l,a.r,sum};
        else if(sum<a.sum) return {l,r,sum};
        else return a;
    }
};
struct node2{
    int t,p;
    inline node2 operator + (const node2 &a)const{
        if(p<=a.p) return {t,p};
        else return a;
    }
};
struct node3{
    int t,p;
    inline node3 operator + (const node3 &a)const{
        if(p>a.p) return {t,p};
        else return a;
    }
};
namespace tree1{
    int rt,segcnt;
    struct tree{
        int ls,rs;
        node1 s;
        int tag;
    }tr[maxn<<1];
    inline void up(int p){tr[p].s=tr[ls(p)].s+tr[rs(p)].s;}
    inline void add(int p,int val){tr[p].s.sum+=val,tr[p].tag+=val;}
    inline void down(int p){if(tr[p].tag) add(ls(p),tr[p].tag),add(rs(p),tr[p].tag);tr[p].tag=0;}
    inline void build(int l,int r,int &p){
        p=++segcnt;
        if(l==r){tr[p].s={l,l,l};return;}
        int mid=(l+r)>>1;
        build(l,mid,ls(p)),build(mid+1,r,rs(p));
        up(p);
    }
    inline void update(int l,int r,int L,int R,int val,int p){
        if(l>=L&&r<=R){add(p,val);return;}
        int mid=(l+r)>>1;down(p);
        if(L<=mid) update(l,mid,L,R,val,ls(p));
        if(R>mid) update(mid+1,r,L,R,val,rs(p));
        up(p);
    }
    inline node1 query(int l,int r,int L,int R,int p){
        if(l>=L&&r<=R) return tr[p].s;
        int mid=(l+r)>>1;down(p);
        if(R<=mid) return query(l,mid,L,R,ls(p));
        if(L>mid) return query(mid+1,r,L,R,rs(p));
        return query(l,mid,L,R,ls(p))+query(mid+1,r,L,R,rs(p));
    }
}
namespace tree2{
    int rt,segcnt;
    struct tree{
        int ls,rs;
        multiset<int> s;
        node2 mn;
    }tr[maxn<<1];
    inline void up(int p){tr[p].mn=tr[ls(p)].mn+tr[rs(p)].mn;}
    inline void build(int l,int r,int &p){
        p=++segcnt;
        if(l==r){tr[p].mn={l,inf};return;}
        int mid=(l+r)>>1;
        build(l,mid,ls(p)),build(mid+1,r,rs(p));
        up(p);
    }
    inline void add(int l,int r,int pos,int val,int p){
        if(l==r){
            tr[p].s.insert(val);
            tr[p].mn.p=min(tr[p].mn.p,val);
            return;
        }
        int mid=(l+r)>>1;
        if(pos<=mid) add(l,mid,pos,val,ls(p));
        else add(mid+1,r,pos,val,rs(p));
        up(p);
    }
    inline void del(int l,int r,int pos,int val,int p){
        if(l==r){
            tr[p].s.erase(tr[p].s.find(val));
            if(tr[p].s.empty()) tr[p].mn.p=inf;
            else tr[p].mn.p=*tr[p].s.begin();
            return;
        }
        int mid=(l+r)>>1;
        if(pos<=mid) del(l,mid,pos,val,ls(p));
        else del(mid+1,r,pos,val,rs(p));
        up(p);
    }
    inline bool find(int l,int r,int pos,int val,int p){
        if(l==r) return tr[p].s.count(val);
        int mid=(l+r)>>1;
        if(pos<=mid) return find(l,mid,pos,val,ls(p));
        else return find(mid+1,r,pos,val,rs(p));
    }
    inline node2 query(int l,int r,int L,int R,int p){
        if(l>=L&&r<=R) return tr[p].mn;
        int mid=(l+r)>>1;
        if(R<=mid) return query(l,mid,L,R,ls(p));
        if(L>mid) return query(mid+1,r,L,R,rs(p));
        return query(l,mid,L,R,ls(p))+query(mid+1,r,L,R,rs(p));
    }
}
namespace tree3{
    int rt,segcnt;
    struct tree{
        int ls,rs;
        multiset<int,greater<int>> s;
        node3 mx;
    }tr[maxn<<1];
    inline void up(int p){tr[p].mx=tr[ls(p)].mx+tr[rs(p)].mx;}
    inline void build(int l,int r,int &p){
        p=++segcnt;
        if(l==r){tr[p].mx={l,-inf};return;}
        int mid=(l+r)>>1;
        build(l,mid,ls(p)),build(mid+1,r,rs(p));
        up(p);
    }
    inline void add(int l,int r,int pos,int val,int p){
        if(l==r){
            tr[p].s.insert(val);
            tr[p].mx.p=max(tr[p].mx.p,val);
            return;
        }
        int mid=(l+r)>>1;
        if(pos<=mid) add(l,mid,pos,val,ls(p));
        else add(mid+1,r,pos,val,rs(p));
        up(p);
    }
    inline void del(int l,int r,int pos,int val,int p){
        if(l==r){
            tr[p].s.erase(tr[p].s.find(val));
            if(tr[p].s.empty()) tr[p].mx.p=-inf;
            else tr[p].mx.p=*tr[p].s.begin();
            return;
        }
        int mid=(l+r)>>1;
        if(pos<=mid) del(l,mid,pos,val,ls(p));
        else del(mid+1,r,pos,val,rs(p));
        up(p);
    }
    inline node3 query(int l,int r,int L,int R,int p){
        if(l>=L&&r<=R) return tr[p].mx;
        int mid=(l+r)>>1;
        if(R<=mid) return query(l,mid,L,R,ls(p));
        if(L>mid) return query(mid+1,r,L,R,rs(p));
        return query(l,mid,L,R,ls(p))+query(mid+1,r,L,R,rs(p));
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;string c;
    tree1::build(1,n,tree1::rt),tree2::build(1,n,tree2::rt),tree3::build(1,n,tree3::rt);
    for(re int i=1,t,p;i<=m;++i){
        cin>>c>>t>>p;
        if(c=="ADD"){
            node1 res=tree1::query(1,n,t,n,1);
            if(res.sum>0){
                ans+=p;
                tree1::update(1,n,t,n,-1,1);
                tree2::add(1,n,t,p,1);
            }	
            else{
                node2 tmp=tree2::query(1,n,1,res.l,1);
                if(tmp.p>p) tree3::add(1,n,t,p,1);
                else{
                    ans+=p-tmp.p;
                    tree1::update(1,n,tmp.t,n,1,1);
                    tree2::del(1,n,tmp.t,tmp.p,1);
                    tree3::add(1,n,tmp.t,tmp.p,1);
                    tree1::update(1,n,t,n,-1,1);
                    tree2::add(1,n,t,p,1);
                }
            }
        }
        else{
            if(!tree2::find(1,n,t,p,1)) tree3::del(1,n,t,p,1);
            else{
                ans-=p;
                tree1::update(1,n,t,n,1,1);
                tree2::del(1,n,t,p,1);
                node1 res=tree1::query(1,n,1,n,1);
                int pos=(res.sum<=0?res.r:0);
                if(pos<n){
                    node3 tmp=tree3::query(1,n,pos+1,n,1);
                    if(tmp.p!=-inf){
                        ans+=tmp.p;
                        tree1::update(1,n,tmp.t,n,-1,1);
                        tree2::add(1,n,tmp.t,tmp.p,1);
                        tree3::del(1,n,tmp.t,tmp.p,1);
                    }
                }
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

[HNOI2015] 开店

本题有点分树做法和树剖主席树做法。

我写了点分树做法，树剖主席树可以看之前的一篇总结。

如果没有年龄限制，怎么做？

先建出点分树，对每个点维护 $sum1_u$ 表示点分树上 $u$ 子树所有点到 $u$ 的距离和，$sum2_u$ 表示点分树上 $u$ 子树所有点到 $u$ 的点分树上父亲的距离和。

设查询点为 $x$，当前跳到点 $u$。

查询时，在点分树上跳父亲，且跳的时候加上

$$sum1_{fa_u}-sum2_u+(siz_{fa_u}-siz_u)\times dis_{x,fa_u}$$

现在有了年龄限制，那么在存信息的时候多开一维，把年龄限制也算上。

然后按年龄排序，做个前缀和，查询时只需要差分一下即可。

代码是很久以前写的。

#include"bits/stdc++.h"
#define int long long
#define re register
using namespace std;
const int maxn=2e5+10;
int n,m,Q,cnt,num,rt,lst,s1,s2;
int a[maxn],head[maxn],siz[maxn],mx[maxn],dfa[maxn];
bitset<maxn> vis;
struct node{
    int fi,se;
    bool operator < (const node &a) const {
        return fi<a.fi;
    }
};
vector<node> sum1[maxn],sum2[maxn];
struct edge{
    int to,nxt,w;
}e[maxn<<1];
struct node1{
    int fa,dep,siz,top,hson,dis;
}t[maxn];
inline void add(int u,int v,int w){
    e[++cnt]={v,head[u],w};
    head[u]=cnt;
}
inline void dfs1(int u,int fa){
    t[u].fa=fa;
    t[u].siz=1;
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        t[v].dep=t[u].dep+1;
        t[v].dis=t[u].dis+e[i].w;
        dfs1(v,u);
        t[u].siz+=t[v].siz;
        if(!t[u].hson||t[v].siz>t[t[u].hson].siz) t[u].hson=v; 
    }
}
inline void dfs2(int u,int top){
    t[u].top=top;
    if(!t[u].hson) return;
    dfs2(t[u].hson,top);
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==t[u].fa||v==t[u].hson) continue;
        dfs2(v,v);
    }
}
inline int lca(int u,int v){
    while(t[u].top!=t[v].top){
        if(t[t[u].top].dep<t[t[v].top].dep) swap(u,v);
        u=t[t[u].top].fa;
    }
    return (t[u].dep<t[v].dep?u:v);
}
inline int getdis(int u,int v){return t[u].dis+t[v].dis-(t[lca(u,v)].dis<<1);}
inline void getrt(int u,int fa){
    siz[u]=1,mx[u]=0;
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v]||v==fa) continue;
        getrt(v,u);
        siz[u]+=siz[v],mx[u]=max(mx[u],siz[v]);
    }
    mx[u]=max(mx[u],num-siz[u]);
    if(mx[u]<mx[rt]||!rt) rt=u;
}
inline void dfs3(int u,int fa,int dep){
    sum1[rt].push_back({a[u],dep});
    if(dfa[rt]) sum2[rt].push_back({a[u],getdis(u,dfa[rt])});
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v]||v==fa) continue;
        dfs3(v,u,dep+e[i].w);
    }
}
inline void dfs(int u){
    vis[u]=1;dfs3(u,0,0);
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v]) continue;
        num=siz[v],rt=0;
        getrt(v,u);
        dfa[rt]=u;
        dfs(rt);
    }
}
inline void build(){
    num=n,rt=0;
    getrt(1,0);
    dfs(rt);
}
inline int query1(int u,int l,int r){
    int L=lower_bound(sum1[u].begin(),sum1[u].end(),node{l,0})-sum1[u].begin()-1;
    int R=upper_bound(sum1[u].begin(),sum1[u].end(),node{r,0})-sum1[u].begin()-1;
    s1=R-L;
    int res=0;
    if(L>=0&&L<sum1[u].size()) res-=sum1[u][L].se;
    if(R>=0&&R<sum1[u].size()) res+=sum1[u][R].se;
    return res;
}
inline int query2(int u,int l,int r){
    int L=lower_bound(sum2[u].begin(),sum2[u].end(),node{l,0})-sum2[u].begin()-1;
    int R=upper_bound(sum2[u].begin(),sum2[u].end(),node{r,0})-sum2[u].begin()-1;
    s2=R-L;
    int res=0;
    if(L>=0&&L<sum2[u].size()) res-=sum2[u][L].se;
    if(R>=0&&R<sum2[u].size()) res+=sum2[u][R].se;
    return res;
}
inline int query(int u,int l,int r){
    int now=u,res=query1(u,l,r);
    while(now){
        res-=query2(now,l,r);
        if(dfa[now]) res+=query1(dfa[now],l,r),res+=(s1-s2)*getdis(u,dfa[now]);
        now=dfa[now];
    }
    return res;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>Q>>m;
    for(re int i=1;i<=n;++i) cin>>a[i];
    for(re int i=1,u,v,w;i<n;++i) cin>>u>>v>>w,add(u,v,w),add(v,u,w);
    dfs1(1,0),dfs2(1,1),build();
    for(re int i=1;i<=n;++i){
        sort(sum1[i].begin(),sum1[i].end());
        sort(sum2[i].begin(),sum2[i].end());
        for(re int j=1;j<sum1[i].size();++j) sum1[i][j].se+=sum1[i][j-1].se;
        for(re int j=1;j<sum2[i].size();++j) sum2[i][j].se+=sum2[i][j-1].se;
    }
    while(Q--){
        int u,l,r,a,b;
        cin>>u>>a>>b;
        l=min((a+lst)%m,(b+lst)%m);
        r=max((a+lst)%m,(b+lst)%m);
        cout<<(lst=query(u,l,r))<<'\n';
    }
    return 0;
}

算术天才⑨与等差数列

写了维护平方和草过去了。

正解还是看题解吧，我不太喜欢做这种哈希题，感觉一直不太理解？

Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流

模板题。

想要详细学习推荐ix35巨佬的博客。

「Wdoi-1」四重存在

我的第一道曼哈顿距离转切比雪夫距离,差点独立切掉。

以下是我的思路：

曼哈顿距离不好做，考虑转化成切比雪夫距离。

然后对于计算答案，我们考虑钦定在编号大的点计算。

转化为切比雪夫距离后，$x_i$ 和 $y_i$ 显然独立，所以下面只考虑一种。

那么问题变为：求 $\max_{i=1}^n \max_{j<i} |x_i-x_j|+v_i$。

把绝对值拆开，发现只需要找大于 $x_i$ 的最大值和小于 $x_i$ 的最小值即可。

现在已经可以支持前两个操作了，考虑操作三。

因为要去掉一个，所以得记录下来最优解点对 $(i,j)$。

如果去掉 $j$，那比较好办，我们对于 $i$ 维护次优解即可。

但去掉 $i$ 呢？

不会了。

以下是正解：

对于最优解点对 $(i,j)$，设它产生的价值为 $w$，那么我们把区间 $[1,i-1],[i+1,j-1],[j+1,n]$ 都和 $w$ 取 $\max$。

那么查询时只需要单点查即可。

也就是说，我们维护一颗线段树，位置 $x$ 表示去掉点 $x$ 时的最大价值。

那么线段树要维护的操作为：区间最值，单点查询。

可以用吉司机线段树，不过好像有简单做法。

upd：直接标记永久化就好了啊。

代码这样写就可以。

inline void update(int l,int r,int L,int R,int val,int p){
    if(L>R) return;
    if(l>=L&&r<=R){tr[p].mx=max(tr[p].mx,val);return;}
    int mid=(l+r)>>1;
    if(L<=mid) update(l,mid,L,R,val,ls(p));
    if(R>mid) update(mid+1,r,L,R,val,rs(p));
}
inline int query(int l,int r,int pos,int p){
    if(l==r) return tr[p].mx;
    int mid=(l+r)>>1;
    if(pos<=mid) return max(tr[p].mx,query(l,mid,pos,ls(p)));
    else return max(tr[p].mx,query(mid+1,r,pos,rs(p)));
}

然后具体说一下怎么维护之前那个式子。

一开始我还想上数据结构，结果发现根本不用。

可以发现，对于一个新加入的点 $i$，能让 $\max_{j<i} |x_i-x_j|$ 取到最大的 $x_j$ 一定是 $x$ 的最大值或最小值，所以直接维护最大值和最小值即可。

但因为我们有操作三，所以还需要维护次大值和次小值。

别忘了还有 $y$，跟上面说的一堆的处理完全相同。

[Cnoi2019] 须臾幻境

原题：BZOJ3514

绷，原题是以前讲课题，当时讲课的时候好像就没想出来。

我会离线！

如果能想到莫队，那基本上就做完了。

加边好做删边困难，容易想到回滚莫队。

那怎么维护答案？并查集！

因为要支持撤销，所以要用可撤销并查集。

然而这题强制在线，所以上面说的并没有什么用。

好久没碰过 LCT 了，对 LCT 不太熟悉了啊。

首先有结论：无环图的连通块个数等于点数-边数。

所以我们考虑维护原图的生成树森林。

考虑用 LCT 维护以时间为边权的最大生成树。加入一条边时，如果会形成环，那就找到最早的一条边断掉。

设一条边被删除的时间为 $t_i$，那么查询的答案为 $n-\sum_{i=l}^r [t_i<l]$。

因为对于 $t_i<l$ 的一条边，它连上后一定会连接两个连通块，使得答案 -1。

数组 $t_i$ 可以在 LCT 维护过程中都求出来，然后就是这个区间查询：区间查小于 $x$ 的数的个数，强制在线。

这二维数点怎么做都行吧，但大部分人好像都写了主席树。

纯粹的弹幕地狱

题意不明题。

以下的 $n$ 为原题中的 $n+1$。

首先把期望用定义拆开，那么就要求概率和价值。

概率转化为计数：受伤的方案数除以总方案数。

连线不经过任何其他格点，这是经典结论：设两点坐标分别为 $(x_1,y_1),(x_2,y_2)$，则不经过任何其他格点的充要条件为 $\gcd(|x_1-x_2|,|y_1-y_2|)=1$。

但这里题目没有说清楚，按理来说在同一行和同一列的情况是经过了其他格点的，但是也得算上。

设 $i=|x_1-x_2|,j=|y_1-y_2|$。

对于一对 $(i,j)$，合法的方案数为 $4(n-i)(n-j)$（因为点对有序，所以分四个方向分别算）。

所以受伤方案数为

$$4n(n-1)+\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}4(n-i)(n-j)[\gcd(i,j)=1]$$

后面这东西莫反直接写了

$$\begin{align*} \sum_{i=1}^{n-1}\sum_{j=1}^{n-1}4(n-i)(n-j)[\gcd(i,j)=1] &=4\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}(n^2-(i+j)n+ij)[\gcd(i,j)=1] \\ &=4\sum_{d=1}^{n-1}\mu(d)\sum_{i=1}^{\lfloor \frac {n-1}{d} \rfloor}\sum_{j=1}^{\lfloor \frac {n-1}{d} \rfloor}(n^2-(i+j)dn+ijd^2) \\ &=4\sum_{d=1}^{n-1}\mu(d)(n^2\lfloor \frac {n-1}{d} \rfloor^2-nd\lfloor \frac {n-1}{d} \rfloor^2(\lfloor \frac {n-1}{d} \rfloor+1)+d^2\frac{\lfloor \frac {n-1}{d} \rfloor^2(\lfloor \frac {n-1}{d} \rfloor+1)^2}{4}) \end{align*}$$

显然可以整除分块。

所以受伤概率为

$$\frac{4n(n-1)+4\sum_{d=1}^{n-1}\mu(d)(n^2\lfloor \frac {n-1}{d} \rfloor^2-nd\lfloor \frac {n-1}{d} \rfloor^2(\lfloor \frac {n-1}{d} \rfloor+1)+d^2\frac{\lfloor \frac {n-1}{d} \rfloor^2(\lfloor \frac {n-1}{d} \rfloor+1)^2}{4})}{n^2}$$

显然每回合受伤概率相同，设概率为 $p$，则期望伤害为

$$p\sum_{x=1}^k ax^2+bx+c=p(a\frac{k(k+1)(2k+1)}{6}+b\frac{k(k+1)}{2}+ck)$$

复杂度 $O(n+\sqrt n)$，瓶颈在预处理。

[SHOI2016] 黑暗前的幻想乡

矩阵树定理+容斥原理好题。

刚学矩阵树的时候就做过这道题。

要求每条边颜色都不相同的生成树数量，直接求是不好求的。

但 $n$ 很小，所以可以考虑容斥。

我们暴力枚举用哪些颜色的边，然后矩阵树定理求出这种情况下的生成树数量，然后再乘上相应的容斥系数即可。

复杂度 $O(2^nn^3)$

「Wdoi-6」最澄澈的空与海

厉害结论题，我被秒杀了。

结论：对于一张左部点和右部点点数相同的二分图，其有且仅有一个完美匹配的必要条件为存在一个节点的入度为 $1$。

证明：考虑反证法。

假设每个点的入度都大于等于 $2$。

我们用 $u_i$ 表示左部点中的第 $i$ 个点，$v_j$ 表示右部点中的第 $j$ 个点。

我们把该图的唯一完美匹配的所有边都删掉，然后在剩下的边中，把 $u_i\rightarrow v_j$ 的边变为一张 $n$ 个点的有向图中的边 $i\rightarrow j$。

那么该有向图中每个点都有出边，必然存在环 $\lbrace c_1,c_2,\cdots,c_k\rbrace$。

则在原二分图中 $\forall \ i,\exists \ u_{c_i}\rightarrow v_{c_{i\operatorname{mod} \ k+1}}$。

我们把原匹配中的边 $\lbrace (u_{c_i}\rightarrow v_{s_{c_i}}),\cdots\rbrace$ 换成 $\lbrace (u_{c_i}\rightarrow v_{s_{c_{i\operatorname{mod} \ k+1}}}),\cdots\rbrace$ 即可得到一个新的匹配。

实现方面，我们可以对这张二分图“拓扑排序”。

每次找到入度为 $1$ 的点 $u$ 入队，然后找到和 $u$ 相连的点 $v$，把点 $u,v$ 删掉。

然后找到所有活着的和点 $v$ 连着的点，把它们的入度 -1。

若最后删除的点的数量为 $2n$，则说明合法。

[MtOI2019] 幽灵乐团 / 莫比乌斯反演基础练习题

终于鼓起勇气写这道题了。

如果你见的套路还不够多，那么建议先去写点别的简单莫反再来挑战这道题。

先拆 $\operatorname{lcm}$：

$$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C (\frac {i\times j}{\gcd(i,k)\times \gcd (i,j)})^{f(type)}$$

那么只需要处理 $\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C i^{f(type)}$ 和 $\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C \gcd(i,j)^{f(type)}$ 即可。

type = 0

算分子部分：

$$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C i$$

这东西很好算吧，易得为：

$$A!^{BC}$$

然后是分母：

$$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C \gcd(i,j)=(\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j))^C$$

这不是天守阁的地板吗？

套路枚举 $\gcd$，得

$$(\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j))^C=(\prod_{d=1} d^{\sum_{i=1}^A\sum_{j=1}^B[\gcd(i,j)=d]})^C$$

指数部分经典莫反，直接写了

$$(\prod_{d=1} d^{\sum_{i=1}^A\sum_{j=1}^B[\gcd(i,j)=d]})^C=(\prod_{d=1} d^{\sum_{p=1}\mu(p)\lfloor \frac {A}{dp} \rfloor\lfloor \frac {B}{dp} \rfloor})^C$$

看到枚举的变量乘在一起了，考虑枚举 $t=dp$，得

$$(\prod_{d=1} d^{\sum_{p=1}\mu(p)\lfloor \frac {A}{dp} \rfloor\lfloor \frac {B}{dp} \rfloor})^C=(\prod_{t=1}(\prod_{d|t} d^{\mu(\frac {t}{d})})^{\lfloor \frac {A}{t} \rfloor\lfloor \frac {B}{t} \rfloor})^C$$

里面这东西显然可以枚举倍数做到 $O(n\log n)$ 预处理，剩下的整除分块可做到 $O(\sqrt n\log n)$。

type = 1

要稍微上难度了。

算分子部分：

$$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C i^{i\times j\times k}$$

把 $j,k$ 放到指数上变为求和，得

$$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C i^{i\times j\times k}=\prod_{i=1}^Ai^{\sum_{j=1}^B\sum_{k=1}^Ci\times j\times k}$$

设 $F(n)=\sum_{i=1}^n$，则

$$\prod_{i=1}^Ai^{\sum_{j=1}^B\sum_{k=1}^Ci\times j\times k}=(\prod_{i=1}^Ai^i)^{F(B)\times F(C)}$$

里面 $O(n\log n)$ 预处理即可。

然后是分母：

$$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C \gcd(i,j)^{i\times j\times k}$$

先把 $k$ 放指数上，得

$$\begin{align*} \prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C \gcd(i,j)^{i\times j\times k} &=\prod_{i=1}^A\prod_{j=1}^B \gcd(i,j)^{\sum_{k=1}^C i\times j\times k} \\ &=(\prod_{i=1}^A\prod_{j=1}^B \gcd(i,j)^{i\times j})^{F(C)} \end{align*}$$

看到里面这东西，直接算肯定算不了，于是依旧考虑枚举 $\gcd$：

$$(\prod_{i=1}^A\prod_{j=1}^B \gcd(i,j)^{i\times j})^{F(C)}=(\prod_{d=1} d^{\sum_{i=1}^A\sum_{j=1}^B i\times j\times [\gcd(i,j)=d]})^{F(C)}$$

指数部分就是[国家集训队] Crash的数字表格 / JZPTAB。

但我有点忘了，为了防止以后不会，下面把它推的过程详细写出来。

$$\sum_{i=1}^A\sum_{j=1}^B i\times j\times [\gcd(i,j)=d]=\sum_{i=1}^A\sum_{j=1}^B i\times j\times [\gcd(\frac{i}{d},\frac{j}{d})=1]$$

把枚举 $i,j$ 换为枚举 $\frac {i}{d},\frac {j}{d}$，得（下面的 $i',j'$ 是原来枚举的 $i,j$）

$$\begin{align*} \sum_{i'=1}^A\sum_{j'=1}^B i'\times j'\times [\gcd(\frac{i'}{d},\frac{j'}{d})=1] &= \sum_{i=1}^{\lfloor \frac {A}{d} \rfloor}\sum_{j=1}^{\lfloor \frac {B}{d} \rfloor} (id)\times (jd)\times [\gcd(i,j)=1] \\ &=d^2\sum_{i=1}^{\lfloor \frac {A}{d} \rfloor}\sum_{j=1}^{\lfloor \frac {B}{d} \rfloor} i\times j\times [\gcd(i,j)=1] \\ &=d^2\sum_{i=1}^{\lfloor \frac {A}{d} \rfloor}\sum_{j=1}^{\lfloor \frac {B}{d} \rfloor} i\times j\sum_{p|\gcd(i,j)} \mu(p) \\ &=d^2\sum_{p=1} \mu(p)\sum_{i=1}^{\lfloor \frac {A}{d} \rfloor}i\times [p|i]\sum_{j=1}^{\lfloor \frac {B}{d} \rfloor} j\times [p|j] \end{align*}$$

把枚举 $i,j$ 换为枚举 $\frac {i}{p},\frac {j}{p}$，得（下面的 $i',j'$ 是原来枚举的 $i,j$）

$$\begin{align*} d^2\sum_{p=1} \mu(p)\sum_{i'=1}^{\lfloor \frac {A}{d} \rfloor}i'\times [p|i']\sum_{j'=1}^{\lfloor \frac {B}{d} \rfloor} j'\times [p|j'] &= d^2\sum_{p=1} \mu(p)\sum_{i=1}^{\lfloor \frac {A}{dp} \rfloor}ip\sum_{j=1}^{\lfloor \frac {B}{dp} \rfloor} jp \\ &=d^2\sum_{p=1} \mu(p)p^2\sum_{i=1}^{\lfloor \frac {A}{dp} \rfloor}i\sum_{j=1}^{\lfloor \frac {B}{dp} \rfloor} j \\ &=d^2\sum_{p=1} \mu(p)p^2F(\lfloor \frac {A}{dp} \rfloor)F(\lfloor \frac {B}{dp} \rfloor) \end{align*}$$

现在可以代回去了：

$$(\prod_{d=1} d^{\sum_{i=1}^A\sum_{j=1}^B i\times j\times [\gcd(i,j)=d]})^{F(C)}=(\prod_{d=1} d^{d^2\sum_{p=1} \mu(p)p^2F(\lfloor \frac {A}{dp} \rfloor)F(\lfloor \frac {B}{dp} \rfloor)})^{F(C)}$$

看到枚举的变量乘在一起了，考虑枚举 $t=dp$，得

$$\begin{align*} (\prod_{d=1} d^{d^2\sum_{p=1} \mu(p)p^2F(\lfloor \frac {A}{dp} \rfloor)F(\lfloor \frac {B}{dp} \rfloor)})^{F(C)} &= (\prod_{t=1} (\prod_{d|t} d^{d^2 \mu(\frac {t}{d})(\frac {t}{d})^2F(\lfloor \frac {A}{t} \rfloor)F(\lfloor \frac {B}{t} \rfloor)}))^{F(C)} \\ &=(\prod_{t=1} ((\prod_{d|t} d^{t^2 \mu(\frac {t}{d})})^{F(\lfloor \frac {A}{t} \rfloor)F(\lfloor \frac {B}{t} \rfloor)}))^{F(C)} \end{align*}$$

里面这东西显然可以枚举倍数+快速幂做到 $O(n\log^2 n)$ 预处理，剩下的整除分块可做到 $O(\sqrt n\log n)$。

type = 2

困难的来了。

算分子部分：

$$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C i^{\gcd(i,j,k)}$$

依旧枚举 $\gcd$，得

$$\begin{align*} \prod_{d=1}\prod_{i=1}^A i^{d\sum_{j=1}^B\sum_{k=1}^C [\gcd(i,j,k)=d]} &=\prod_{d=1}\prod_{i=1}^{\lfloor \frac {A}{d} \rfloor} (id)^{d\sum_{j=1}^{\lfloor \frac {B}{d} \rfloor}\sum_{k=1}^{\lfloor \frac {C}{d} \rfloor} [\gcd(i,j,k)=1]} \\ &=\prod_{d=1}\prod_{i=1}^{\lfloor \frac {A}{d} \rfloor} (id)^{d\sum_{p=1} \mu(p)[p|i]\sum_{j=1}^{\lfloor \frac {B}{d} \rfloor} [p|j]\sum_{k=1}^{\lfloor \frac {C}{d} \rfloor}[p|k]} \end{align*}$$

枚举 $p$，得

$$\begin{align*} \prod_{d=1}\prod_{i=1}^{\lfloor \frac {A}{d} \rfloor} (id)^{d\sum_{p=1} \mu(p)[p|i]\sum_{j=1}^{\lfloor \frac {B}{d} \rfloor} [p|j]\sum_{k=1}^{\lfloor \frac {C}{d} \rfloor}[p|k]} &=\prod_{d=1}\prod_{p=1}\prod_{i=1}^{\lfloor \frac {A}{dp} \rfloor} (idp)^{d\times \mu(p)\lfloor \frac {B}{dp} \rfloor\lfloor \frac {C}{dp} \rfloor} \end{align*}$$

看到枚举的变量乘在一起了，考虑枚举 $t=dp$，得

$$\begin{align*} \prod_{d=1}\prod_{p=1}\prod_{i=1}^{\lfloor \frac {A}{dp} \rfloor} (idp)^{d\times \mu(p)\lfloor \frac {B}{dp} \rfloor\lfloor \frac {C}{dp} \rfloor} &=\prod_{t=1}\prod_{d|t}\prod_{i=1}^{\lfloor \frac {A}{t} \rfloor} (it)^{d\times \mu(\frac {t}{d})\lfloor \frac {B}{t} \rfloor\lfloor \frac {C}{t} \rfloor} \\ &=\prod_{t=1}\prod_{d|t}(t^{\lfloor \frac {A}{t} \rfloor}\prod_{i=1}^{\lfloor \frac {A}{t} \rfloor}i)^{d\times \mu(\frac {t}{d})\lfloor \frac {B}{t} \rfloor\lfloor \frac {C}{t} \rfloor} \end{align*}$$

发现只有指数上有 $d$，把 $\prod$ 放到指数上变成 $\sum$，得

$$\begin{align*} \prod_{t=1}\prod_{d|t}(t^{\lfloor \frac {A}{t} \rfloor}\prod_{i=1}^{\lfloor \frac {A}{t} \rfloor}i)^{d\times \mu(\frac {t}{d})\lfloor \frac {B}{t} \rfloor\lfloor \frac {C}{t} \rfloor} &=\prod_{t=1}((t^{\lfloor \frac {A}{t} \rfloor}{\lfloor \frac {A}{t} \rfloor}!)^{\sum_{d|t} d\times \mu(\frac {t}{d})})^{\lfloor \frac {B}{t} \rfloor\lfloor \frac {C}{t} \rfloor} \end{align*}$$

发现指数是个经典的狄利克雷卷积，用 $Id*\mu=\varphi$ 换掉：

$$\begin{align*} \prod_{t=1}((t^{\lfloor \frac {A}{t} \rfloor}{\lfloor \frac {A}{t} \rfloor}!)^{\sum_{d|t} d\times \mu(\frac {t}{d})})^{\lfloor \frac {B}{t} \rfloor\lfloor \frac {C}{t} \rfloor} &= \prod_{t=1}(t^{\lfloor \frac {A}{t} \rfloor}{\lfloor \frac {A}{t} \rfloor}!)^{\varphi(t)\lfloor \frac {B}{t} \rfloor\lfloor \frac {C}{t} \rfloor} \\ &=\prod_{t=1}(t^{\varphi(t)})^{\lfloor \frac {A}{t} \rfloor\lfloor \frac {B}{t} \rfloor\lfloor \frac {C}{t} \rfloor}({\lfloor \frac {A}{t} \rfloor}!^{\lfloor \frac {B}{t} \rfloor\lfloor \frac {C}{t} \rfloor})^{\varphi(t)} \end{align*}$$

预处理 $t^{\varphi(t)}$ 的前缀积和 $\varphi(t)$ 的前缀和，复杂度 $O(n\log n)$。

剩下的整除分块 $O(\sqrt n\log n)$。

然后是分母：

$$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C \gcd(i,j)^{\gcd(i,j,k)}$$

已经不太能自己推出来了，参考了题解。

套路的考虑枚举 $\gcd(i,j)$，指数部分根据 $\gcd$ 的结合律会变为：

$$\begin{align*} \prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C \gcd(i,j)^{\gcd(i,j,k)} &=\prod_{d=1}\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C d^{\gcd(d,k)}[\gcd(i,j)=d] \\ &=\prod_{d=1} (d^{\sum_{i=1}^A\sum_{j=1}^B [\gcd(i,j)=d]})^{\sum_{k=1}^C \gcd(d,k)} \end{align*}$$

里面的指数是标准莫反，外面的指数是标准的欧拉反演。

把外面的再写一下。欧拉反演我用的不是很多，也不太熟练。

$$\begin{align*} \sum_{k=1}^C \gcd(d,k) &=\sum_{k=1}^C \sum_{x|\gcd(d,k)}\varphi(x) \\ &=\sum_{x=1} \varphi(x)[x|d]\sum_{k=1}^C [x|k] \\ &=\sum_{x|d} \varphi(x)\lfloor \frac {C}{x} \rfloor \end{align*}$$

代到原式：

$$\prod_{d=1} (d^{\sum_{i=1}^A\sum_{j=1}^B [\gcd(i,j)=d]})^{\sum_{k=1}^C \gcd(d,k)} = \prod_{d=1} (d^{\sum_{p=1}\mu(p)\lfloor \frac {A}{dp} \rfloor\lfloor \frac {B}{dp} \rfloor})^{\sum_{x|d} \varphi(x)\lfloor \frac {C}{x} \rfloor}$$

看到枚举的变量乘在一起了，考虑枚举 $t=dp$，得

$$\begin{align*} \prod_{d=1} (d^{\sum_{p=1}\mu(p)\lfloor \frac {A}{dp} \rfloor\lfloor \frac {B}{dp} \rfloor})^{\sum_{x|d} \varphi(x)\lfloor \frac {C}{x} \rfloor} &=\prod_{t=1} \prod_{d|t}d^{\mu(\frac{t}{d})\lfloor \frac {A}{t} \rfloor\lfloor \frac {B}{t} \rfloor\sum_{x|d} \varphi(x)\lfloor \frac {C}{x} \rfloor} \\ &=\prod_{t=1} \prod_{d|t}\prod_{x|d}d^{\mu(\frac{t}{d})\lfloor \frac {A}{t} \rfloor\lfloor \frac {B}{t} \rfloor\varphi(x)\lfloor \frac {C}{x} \rfloor} \end{align*}$$

要同时枚举 $x,d$，没法化了。

然后题解告诉我们，把 $d$ 拆成 $x$ 和 $\frac {d}{x}$ 分别算，然后再乘起来。

那么先看第一部分：

$$\prod_{t=1} \prod_{d|t}\prod_{x|d}x^{\mu(\frac{t}{d})\lfloor \frac {A}{t} \rfloor\lfloor \frac {B}{t} \rfloor\varphi(x)\lfloor \frac {C}{x} \rfloor}$$

设 $lim=\max(A,B,C)$。把 $x$ 提到最前面枚举，得

$$\begin{align*} \prod_{t=1} \prod_{d|t}\prod_{x|d}x^{\mu(\frac{t}{d})\lfloor \frac {A}{t} \rfloor\lfloor \frac {B}{t} \rfloor\varphi(x)\lfloor \frac {C}{x} \rfloor} &=\prod_{x=1} \prod_{t=1}^{lim}[x|t]\prod_{d|t}[x|d]x^{\mu(\frac{t}{d})\lfloor \frac {A}{t} \rfloor\lfloor \frac {B}{t} \rfloor\varphi(x)\lfloor \frac {C}{x} \rfloor} \end{align*}$$

把枚举 $t,d$ 换为枚举 $\frac {t}{x},\frac {d}{x}$，得（下面的 $t',d'$ 是原来枚举的 $t,d$）

$$\begin{align*} \prod_{x=1} \prod_{t'=1}^{lim}[x|t']\prod_{d'|t'}[x|d']x^{\mu(\frac{t'}{d'})\lfloor \frac {A}{t'} \rfloor\lfloor \frac {B}{t'} \rfloor\varphi(x)\lfloor \frac {C}{x} \rfloor} &=\prod_{x=1} \prod_{t=1}^{\lfloor \frac{lim}{x} \rfloor}\prod_{d|t}x^{\mu(\frac{tx}{dx})\lfloor \frac {A}{tx} \rfloor\lfloor \frac {B}{tx} \rfloor\varphi(x)\lfloor \frac {C}{x} \rfloor} \end{align*}$$

发现只有指数上有 $t,d$，把 $\prod$ 放到指数上变成 $\sum$，得

$$\begin{align*} \prod_{x=1} \prod_{t=1}^{\lfloor \frac{lim}{x} \rfloor}\prod_{d|t}x^{\mu(\frac{tx}{dx})\lfloor \frac {A}{tx} \rfloor\lfloor \frac {B}{tx} \rfloor\varphi(x)\lfloor \frac {C}{x} \rfloor} &=\prod_{x=1}x^{\varphi(x)\lfloor \frac {C}{x} \rfloor\sum_{t=1}^{\lfloor \frac{lim}{x} \rfloor}\lfloor \frac {A}{tx} \rfloor\lfloor \frac {B}{tx} \rfloor\sum_{d|t}\mu(\frac{t}{d})} \end{align*}$$

发现指数是个经典的狄利克雷卷积，用 $\mu*1=\epsilon$ 换掉：

$$\begin{align*} \prod_{x=1}x^{\varphi(x)\lfloor \frac {C}{x} \rfloor\sum_{t=1}^{\lfloor \frac{lim}{x} \rfloor}\lfloor \frac {A}{tx} \rfloor\lfloor \frac {B}{tx} \rfloor\sum_{d|t}\mu(\frac{t}{d})} &=\prod_{x=1}x^{\varphi(x)\lfloor \frac {C}{x} \rfloor\sum_{t=1}^{\lfloor \frac{lim}{x} \rfloor}\lfloor \frac {A}{tx} \rfloor\lfloor \frac {B}{tx} \rfloor[t=1]} \\ &=\prod_{x=1}x^{\varphi(x)\lfloor \frac {A}{x} \rfloor\lfloor \frac {B}{x} \rfloor\lfloor \frac {C}{x} \rfloor} \end{align*}$$

是个和分子部分一样的形式，同样处理即可。

然后看第二部分：

$$\prod_{t=1} \prod_{d|t}\prod_{x|d}(\frac{d}{x})^{\mu(\frac{t}{d})\lfloor \frac {A}{t} \rfloor\lfloor \frac {B}{t} \rfloor\varphi(x)\lfloor \frac {C}{x} \rfloor}$$

依旧把 $x$ 提到最前面枚举，得

$$\begin{align*} \prod_{t=1}^{lim} \prod_{d|t}\prod_{x|d}(\frac{d}{x})^{\mu(\frac{t}{d})\lfloor \frac {A}{t} \rfloor\lfloor \frac {B}{t} \rfloor\varphi(x)\lfloor \frac {C}{x} \rfloor} &=\prod_{x=1}\prod_{t=1}^{lim} [x|t]\prod_{d|t}[x|d](\frac{d}{x})^{\mu(\frac{t}{d})\lfloor \frac {A}{t} \rfloor\lfloor \frac {B}{t} \rfloor\varphi(x)\lfloor \frac {C}{x} \rfloor} \\ &=\prod_{x=1}\prod_{t=1}^{\lfloor \frac{lim}{x} \rfloor} \prod_{d|tx}[x|d](\frac{d}{x})^{\mu(\frac{tx}{d})\lfloor \frac {A}{tx} \rfloor\lfloor \frac {B}{tx} \rfloor\varphi(x)\lfloor \frac {C}{x} \rfloor} \end{align*}$$

把枚举 $t$ 换为枚举 $\frac {t}{x}$，得（下面的 $t'$ 是原来枚举的 $t$）

$$\begin{align*} \prod_{x=1}\prod_{t'=1}^{lim} [x|t']\prod_{d|t'}[x|d](\frac{d}{x})^{\mu(\frac{t'}{d})\lfloor \frac {A}{t'} \rfloor\lfloor \frac {B}{t'} \rfloor\varphi(x)\lfloor \frac {C}{x} \rfloor} &=\prod_{x=1}\prod_{t=1}^{\lfloor \frac{lim}{x} \rfloor} \prod_{d|tx}[x|d](\frac{d}{x})^{\mu(\frac{tx}{d})\lfloor \frac {A}{tx} \rfloor\lfloor \frac {B}{tx} \rfloor\varphi(x)\lfloor \frac {C}{x} \rfloor} \end{align*}$$

把枚举 $d$ 换为枚举 $dx$，得（下面的 $d'$ 是原来枚举的 $d$）

$$\begin{align*} \prod_{x=1}\prod_{t=1}^{\lfloor \frac{lim}{x} \rfloor} \prod_{d'|tx}[x|d'](\frac{d'}{x})^{\mu(\frac{tx}{d'})\lfloor \frac {A}{tx} \rfloor\lfloor \frac {B}{tx} \rfloor\varphi(x)\lfloor \frac {C}{x} \rfloor} &=\prod_{x=1}\prod_{t=1}^{\lfloor \frac{lim}{x} \rfloor} \prod_{d|t}d^{\mu(\frac{t}{d})\lfloor \frac {A}{tx} \rfloor\lfloor \frac {B}{tx} \rfloor\varphi(x)\lfloor \frac {C}{x} \rfloor} \\ &=\prod_{x=1}(\prod_{t=1}^{\lfloor \frac{lim}{x} \rfloor} (\prod_{d|t}d^{\mu(\frac{t}{d})})^{\lfloor \frac {A}{tx} \rfloor\lfloor \frac {B}{tx} \rfloor})^{\varphi(x)\lfloor \frac {C}{x} \rfloor} \\ &=\prod_{x=1}(\prod_{t=1}^{\lfloor \frac{lim}{x} \rfloor} (\prod_{d|t}d^{\mu(\frac{t}{d})})^{\lfloor \frac {\lfloor \frac {A}{x} \rfloor}{t} \rfloor\lfloor \frac {\lfloor \frac {B}{x} \rfloor}{t} \rfloor})^{\varphi(x)\lfloor \frac {C}{x} \rfloor} \end{align*}$$

最里面的东西在之前已经处理过了，然后可以整除分块套整除分块做到 $O(n^{\frac {3}{4}}\log n)$ 的复杂度。

问题得以解决。

听说比较卡常，所以代码有空再写。

upd：好像不太卡常啊，但我取模取少了导致一直死···

一些注意事项：

1. 减法记得加上模数，千万别出负数。
2. 根据欧拉定理，指数应该对 $mod-1$ 取模，而不是 $mod$。

#include"bits/stdc++.h"
#define re register
#define int long long
#define min(a,b) (a<b?a:b)
using namespace std;
const int maxn=1e5+10,V=1e5;
int mod,_mod,A,B,C,cnt;
int fac[maxn],inv[maxn];
int fac1[maxn];
int fac2[maxn],inv_fac2[maxn];
int a[maxn],prod[maxn],inv_prod[maxn];
int b[maxn],prod1[maxn],inv_prod1[maxn];
int tmp_prod[maxn],tmp_inv[maxn];
int pri[maxn];
int mu[maxn],phi[maxn];
int s_phi[maxn];
bitset<maxn> vis;
inline int qpow(int a,int b){
    a%=mod,b%=_mod;
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;   
    }
    return res;
}
inline int Inv(int x){return qpow(x,mod-2);}
inline int F(int x){return (x*(x+1)/2)%_mod;}
inline void sieve(){
    mu[1]=1,phi[1]=1;
    for(re int i=2;i<=V;++i){
        if(!vis[i]) pri[++cnt]=i,mu[i]=-1,phi[i]=i-1;
        for(re int j=1;j<=cnt&&i*pri[j]<=V;++j){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0){phi[i*pri[j]]=phi[i]*pri[j];break;}
            else mu[i*pri[j]]=-mu[i],phi[i*pri[j]]=phi[i]*phi[pri[j]];
        }
    }
    for(re int i=1;i<=V;++i) s_phi[i]=(s_phi[i-1]+phi[i])%_mod;
}
inline void pre_fac(){
    inv[0]=inv[1]=1;
    for(re int i=2;i<=V;++i) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    fac[0]=1;
    for(re int i=1;i<=V;++i) fac[i]=fac[i-1]*i%mod;
    fac1[0]=1;
    for(re int i=1;i<=V;++i) fac1[i]=fac1[i-1]*qpow(i,i)%mod;
    fac2[0]=1;
    for(re int i=1;i<=V;++i) fac2[i]=fac2[i-1]*qpow(i,phi[i])%mod;
    tmp_prod[0]=inv_fac2[0]=1;
    for(re int i=1;i<=V;++i) tmp_prod[i]=tmp_prod[i-1]*fac2[i]%mod;
    tmp_inv[V]=Inv(tmp_prod[V]);
    for(re int i=V-1;i>=1;--i) tmp_inv[i]=tmp_inv[i+1]*fac2[i+1]%mod;
    for(re int i=1;i<=V;++i) inv_fac2[i]=tmp_prod[i-1]*tmp_inv[i]%mod;
}
inline void pre_f1(){
    for(re int i=1;i<=V;++i) a[i]=1;
    for(re int d=1;d<=V;++d){
        for(re int t=d;t<=V;t+=d){
            if(mu[t/d]==-1) a[t]=a[t]*inv[d]%mod;
            if(mu[t/d]==1) a[t]=a[t]*d%mod;
        }
    }
    prod[0]=1;
    for(re int i=1;i<=V;++i) prod[i]=prod[i-1]*a[i]%mod;
    tmp_prod[0]=inv_prod[0]=1;
    for(re int i=1;i<=V;++i) tmp_prod[i]=tmp_prod[i-1]*prod[i]%mod;
    tmp_inv[V]=Inv(tmp_prod[V]);
    for(re int i=V-1;i>=1;--i) tmp_inv[i]=tmp_inv[i+1]*prod[i+1]%mod;
    for(re int i=1;i<=V;++i) inv_prod[i]=tmp_prod[i-1]*tmp_inv[i]%mod;
}
inline void pre_f2(){
    for(re int i=1;i<=V;++i) b[i]=1;
    for(re int d=1;d<=V;++d){
        for(re int t=d;t<=V;t+=d){
            if(mu[t/d]==-1) b[t]=b[t]*Inv(qpow(d,t*t))%mod;
            if(mu[t/d]==1) b[t]=b[t]*qpow(d,t*t)%mod;
        }
    }
    prod1[0]=1;
    for(re int i=1;i<=V;++i) prod1[i]=prod1[i-1]*b[i]%mod;
    tmp_prod[0]=inv_prod1[0]=1;
    for(re int i=1;i<=V;++i) tmp_prod[i]=tmp_prod[i-1]*prod1[i]%mod;
    tmp_inv[V]=Inv(tmp_prod[V]);
    for(re int i=V-1;i>=1;--i) tmp_inv[i]=tmp_inv[i+1]*prod1[i+1]%mod;
    for(re int i=1;i<=V;++i) inv_prod1[i]=tmp_prod[i-1]*tmp_inv[i]%mod;
}
inline void init(){
    sieve();
    pre_fac();
    pre_f1();
    pre_f2();
}
inline int _f2(int a,int b){
    int res=1,lim=min(a,b);
    for(re int l=1,r;l<=lim;l=r+1){
        r=min(a/(a/l),b/(b/l));if(r>lim) r=lim;
        res=res*qpow(prod[r]*inv_prod[l-1],(a/l)*(b/l))%mod;
    }
    return res;
}
inline int f1(int a,int b,int c,int type){
    if(type==0) return qpow(fac[a],b*c);
    if(type==1) return qpow(fac1[a],F(b)*F(c));
    if(type==2){
        int res=1,lim=min(min(a,b),c);
        for(re int l=1,r;l<=lim;l=r+1){
            r=min(min(a/(a/l),b/(b/l)),c/(c/l));if(r>lim) r=lim;
            res=res*qpow(fac2[r]*inv_fac2[l-1],(a/l)*(b/l)%_mod*(c/l))%mod;
            res=res*qpow(fac[a/l],(b/l)*(c/l)%_mod*(s_phi[r]-s_phi[l-1]+_mod)%_mod)%mod;
        }
        return res;
    }
}
inline int f2(int a,int b,int c,int type){
    int res=1;
    if(type==0){
        int lim=min(a,b);
        for(re int l=1,r;l<=lim;l=r+1){
            r=min(a/(a/l),b/(b/l));if(r>lim) r=lim;
            res=res*qpow(prod[r]*inv_prod[l-1],(a/l)*(b/l))%mod;
        }
        res=qpow(res,c);
    }
    if(type==1){
        int lim=min(a,b);
        for(re int l=1,r;l<=lim;l=r+1){
            r=min(a/(a/l),b/(b/l));if(r>lim) r=lim;
            res=res*qpow(prod1[r]*inv_prod1[l-1],F((a/l))*F((b/l)))%mod;
        }
        res=qpow(res,F(c));
    }
    if(type==2){
        int lim=min(min(a,b),c);
        for(re int l=1,r;l<=lim;l=r+1){
            r=min(min(a/(a/l),b/(b/l)),c/(c/l));if(r>lim) r=lim;
            res=res*qpow(fac2[r]*inv_fac2[l-1],(a/l)*(b/l)%_mod*(c/l))%mod;
            res=res*qpow(_f2(a/l,b/l),(s_phi[r]-s_phi[l-1]+_mod)%_mod*(c/l))%mod;
        }
    }
    return res;
}
inline void solve(){
    cin>>A>>B>>C;
    for(re int type=0;type<=2;++type) cout<<f1(A,B,C,type)%mod*f1(B,A,C,type)%mod*Inv(f2(A,B,C,type))%mod*Inv(f2(A,C,B,type))%mod<<' ';
    cout<<'\n';
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T;cin>>T>>mod;_mod=mod-1;init();while(T--) solve();
    cerr<<1.0*clock()/CLOCKS_PER_SEC;
    return 0;
}

符卡对决

感觉和[Cnoi2019] 须臾幻境的离线版很像。

可以发现答案为：$\frac {\text{所有连通块的权值和的平方和-所有点的权值的平方和}}{n(n-1)}$。

区间加边可以套用[Cnoi2019] 须臾幻境那题的做法：回滚莫队+可撤销并查集。

指针移动时维护每个连通块的权值和，然后更新一下答案。

感觉不太会写回滚莫队啊？

upd：竟然在不太会写回滚莫队的情况下一遍过了，基本没调。

#include"bits/stdc++.h"
#define re register
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=1e5+10,maxm=500,mod=1e9+7;
int n,m,Q,siz,tot,bs;
int a[maxn],ans[maxn];
int st[maxm],ed[maxm],bel[maxn<<1];
struct edge{
    int u,v;
}e[maxn<<1];
struct query{
    int l,r,id;
}q[maxn];
struct dsu{
    int fa[maxn],siz[maxn],w[maxn];
    stack<pii> stk;
    inline int find(int x){if(x!=fa[x]) return find(fa[x]);return fa[x];}
    inline void merge(int u,int v,int &now,bool type){
        int x=find(u),y=find(v);
        if(x==y){if(type) stk.push({0,0});return;}
        if(siz[x]<siz[y]) swap(x,y);
        if(type) stk.push({x,y});
        now=((now-w[x]*w[x]%mod-w[y]*w[y]%mod)%mod+mod)%mod;
        siz[x]+=siz[y],fa[y]=x,w[x]=(w[x]+w[y])%mod;
        now=(now+w[x]*w[x]%mod)%mod;
    }
    inline void undo(){
        int x=stk.top().fi,fi,y=stk.top().se;stk.pop();
        fa[y]=y,siz[x]-=siz[y],w[x]=((w[x]-w[y])%mod+mod)%mod;
    }
}t1,t2;
inline bool cmp(query a,query b){
    if(bel[a.l]==bel[b.l]) return a.r<b.r;
    return bel[a.l]<bel[b.l];
}
inline int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod; 
    }
    return res;
}
inline int Inv(int x){return qpow(x,mod-2);}
inline void init(){
    siz=sqrt(m);
    tot=m/siz;
    for(re int i=1;i<=tot;++i) st[i]=(i-1)*siz+1,ed[i]=i*siz;
    if(ed[tot]<m) ++tot,st[tot]=ed[tot-1]+1,ed[tot]=m;
    for(re int i=1;i<=tot;++i) for(re int j=st[i];j<=ed[i];++j) bel[j]=i;
}
inline void solve(int l,int r,int id){
    int res=bs;
    for(re int i=l;i<=r;++i) t2.merge(e[i].u,e[i].v,res,1);
    ans[id]=((res-bs)%mod+mod)%mod;
    for(re int i=l;i<=r;++i) t2.undo();
}
inline void add(int id,int &res,bool type){t1.merge(e[id].u,e[id].v,res,type);}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>Q;
    for(re int i=1;i<=n;++i) cin>>a[i],bs=(bs+a[i]*a[i])%mod;
    for(re int i=1;i<=n;++i) t1.fa[i]=i,t1.siz[i]=1,t1.w[i]=a[i];
    for(re int i=1;i<=n;++i) t2.fa[i]=i,t2.siz[i]=1,t2.w[i]=a[i];
    for(re int i=1;i<=m;++i) cin>>e[i].u>>e[i].v;
    for(re int i=1;i<=Q;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
    init();
    sort(q+1,q+Q+1,cmp);
    int l=1,r=0,lst=0,now=bs;
    for(re int i=1;i<=Q;++i){
        if(bel[q[i].l]==bel[q[i].r]) solve(q[i].l,q[i].r,q[i].id);
        else{
            if(lst^bel[q[i].l]){
                for(re int i=1;i<=n;++i) t1.fa[i]=i,t1.siz[i]=1,t1.w[i]=a[i];
                l=ed[bel[q[i].l]]+1,r=ed[bel[q[i].l]];
                now=bs,lst=bel[q[i].l];
            }
            while(r<q[i].r) add(++r,now,0);
            int tmp=now,l1=l;
            while(l1>q[i].l) add(--l1,tmp,1);
            ans[q[i].id]=((tmp-bs)%mod+mod)%mod;
            while(l1<l) l1++,t1.undo();
        }
    }
    for(re int i=1;i<=Q;++i) cout<<ans[i]*Inv(n*(n-1)%mod)%mod<<'\n';
    return 0;
}

「Wdsr-2.7」文文的摄影布置

思路又错了···

我的思路：

首先考虑全局询问怎么做。

一种显然的想法是枚举 $j$，然后找前面的最大值和后面的最大值。

现在变为区间询问还带修，考虑线段树维护。

我们对一个区间维护它的最优决策点，然后考虑合并两个区间。

然后就没有然后了···

因为仔细思考一下，会发现有一堆问题。

正解思路：

我们不枚举 $j$，而是考虑 $i,k$。

考虑怎么合并两个区间。

如果 $(i,j,k)$ 都在左/右儿子，那直接继承答案。

如果 $i$ 在左儿子，$k$ 在右儿子，那么考虑 $j$ 在哪。

如果 $j$ 在左儿子，那么需要得到左儿子的 $\max_{i<j} a_i-b_j$ 和右儿子的 $\max a_k$。

如果 $j$ 在右儿子，那么需要得到左儿子的 $\max a_i$ 和右儿子的 $\max_{j<k} a_k-b_j$。

然后考虑怎么维护 $\max_{i<j} a_i-b_j$。

依旧考虑合并。

若 $i,j$ 都在左/右儿子，那直接继承答案。

若 $i$ 在左儿子，$j$ 在右儿子，那么需要得到左儿子的 $\max a_i$ 和右儿子的 $\min b_j$。

另一个维护同理。

「Wdoi-2」纯粹的复仇女神

这次思路对了，想到了扫描线，然后不会做了哈哈。

事实上第一眼想的是莫队，然后发现不好删除，于是考虑回滚莫队。

但看到标签是线段树所以没细想，事后在题解区发现大力卡常还真能过。

正解思路：

我们将询问离线扫描线，假设当前扫到的右端点为 $r$。

因为每种颜色独立，我们只把其中一种拿出来看。

可以发现，当右端点 $r$ 固定时，左端点向左扫，某个元素会成为最小值所对应的左端点是一段区间。

所以我们把每个位置能成为最小值的区间找出来，处理区间可以用单调栈。

然后扫描线。

当扫到一个点时，把它加进去；当前扫到的右端点已经不在这个点的区间里时，把它扔掉。

然后可以在线段树上每个节点维护一个可删堆，修改时标记永久化。

「Wdsr-2.7」八云蓝自动机 Ⅰ

做了这么久题还是只会 $\le$ 板子难度的题，唉。

首先考虑没有单点修改怎么做。

我们维护以下信息：

• 序列 $a$ 操作后的状态。
• 原位置 $i$ 现在的位置，记作 $pos_i$。
• 现位置 $i$ 原来的位置，记作 $rev_i$。
• 现位置 $i$ 的贡献次数，记作 $num_i$。

然后考虑指针移动带来的影响。

当右指针右移时：

• 若操作为交换 $x,y$，则交换 $a_x$ 和 $a_y$，$rev_x$ 和 $rev_y$，$num_x$ 和 $num_y$，$pos_{rev_x}$ 和 $pos_{rev_y}$。
• 若操作为查询 $x$，则 $ans \leftarrow ans+a_x$，$num_x \leftarrow num_x+1$。

当左指针左移时：

因为在实际的操作时，这个操作是最先进行的，所以这个操作会对后面的操作都有影响。

因为这个操作是最先进行的，所以它操作的位置都是最初始的位置，对应到当前的序列上即为 $pos_i$。

• 若操作为查询 $x$，则 $ans \leftarrow ans+a_{pos_x}$，$num_{pos_x} \leftarrow num_{pos_x}+1$。
• 若操作为交换 $x,y$，则交换 $pos_x$ 和 $pos_y$，$a_{pos_x}$ 和 $a_{pos_y}$，$rev_{pos_x}$ 和 $rev_{pos_y}$。因为交换操作对后面的查询都有影响，所以还要考虑对答案的影响，则 $ans \leftarrow ans+(a_{pos_x}-a_{pos_y})\times (num_{pos_x}-num_{pos_y})$。

缩小区间的指针移动同理。

然后考虑带上单点修改怎么做。

我们可以新建一堆点，然后把单点修改转化为交换操作。

我对这道题的理解也就仅限能理解了，再遇到这种题估计还是没思路···

代码贺的。

#include"bits/stdc++.h"
#define re register
// #define int long long
#define uint unsigned int
using namespace std;
const int maxn=4e5+10,maxm=2e5+10;
int n,m,Q,siz;
uint now,a[maxn],ans[maxm],pos[maxn],rev[maxn],num[maxn];
struct change{
    int op,x,y;
}t[maxm];
struct query{
    int l,r,id;
}q[maxm];
inline bool cmp(query a,query b){return ((a.l/siz)^(b.l/siz))?(a.l/siz)<(b.l/siz):((a.l/siz)&1)?a.r<b.r:a.r>b.r;}
inline void add1(int id){
    if(t[id].op==2){
        swap(a[t[id].x],a[t[id].y]);
        swap(rev[t[id].x],rev[t[id].y]);
        swap(num[t[id].x],num[t[id].y]);
        swap(pos[rev[t[id].x]],pos[rev[t[id].y]]);
    }
    else{
        now+=a[t[id].x];
        ++num[t[id].x];
    }
}
inline void add2(int id){
    if(t[id].op==2){
        swap(pos[t[id].x],pos[t[id].y]);
        swap(a[pos[t[id].x]],a[pos[t[id].y]]);
        swap(rev[pos[t[id].x]],rev[pos[t[id].y]]);
        now+=(a[pos[t[id].x]]-a[pos[t[id].y]])*(num[pos[t[id].x]]-num[pos[t[id].y]]);
    }
    else{
        now+=a[pos[t[id].x]];
        ++num[pos[t[id].x]];
    }
}
inline void del1(int id){
    if(t[id].op==2){
        swap(a[t[id].x],a[t[id].y]);
        swap(rev[t[id].x],rev[t[id].y]);
        swap(num[t[id].x],num[t[id].y]);
        swap(pos[rev[t[id].x]],pos[rev[t[id].y]]);
    }
    else{
        now-=a[t[id].x];
        --num[t[id].x];
    }
}
inline void del2(int id){
    if(t[id].op==2){
        now-=(a[pos[t[id].x]]-a[pos[t[id].y]])*(num[pos[t[id].x]]-num[pos[t[id].y]]);
        swap(pos[t[id].x],pos[t[id].y]);
        swap(a[pos[t[id].x]],a[pos[t[id].y]]);
        swap(rev[pos[t[id].x]],rev[pos[t[id].y]]);
    }
    else{
        now-=a[pos[t[id].x]];
        --num[pos[t[id].x]];
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1;i<=n;++i) cin>>a[i];
    for(re int i=1,op,x,y;i<=m;++i){
        cin>>op>>x;
        if(op==1){y=++n;cin>>a[n];op=2;}
        else if(op==2) cin>>y;
        t[i]={op,x,y};
    }
    for(re int i=1;i<=n;++i) pos[i]=rev[i]=i;
    cin>>Q;
    for(re int i=1;i<=Q;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
    siz=sqrt(m);
    sort(q+1,q+Q+1,cmp);
    int l=1,r=0;
    for(re int i=1;i<=Q;++i){
        while(r<q[i].r) add1(++r);
        while(l>q[i].l) add2(--l);
        while(r>q[i].r) del1(r--);
        while(l<q[i].l) del2(l++);
        ans[q[i].id]=now;
    }
    for(re int i=1;i<=Q;++i) cout<<ans[i]<<'\n';
    return 0;
}

[Cnoi2021] 未来试题

不会套路题了不会套路题了不会套路题了不会套路题了不会套路题了

弱化版：[COCI2006-2007#4] ZBRKA

先来看弱化版怎么做。

对于这种排列计数问题，套路的状态设计是设 $f_i$ 表示将 $1\sim i$ 填入排列的方案数，后面的维度可以按照所求补充，然后考虑新加入一个数对答案产生的贡献。

那么这道题要求逆序对数，所以设 $f_{i,j}$ 表示将 $1\sim i$ 填入排列，逆序对数为 $j$ 的方案数。

转移就是考虑把 $i$ 放到哪里。因为 $i$ 比 $1\sim i-1$ 都要大，所以把 $i$ 放到 $k$ 个数前面就会产生 $k$ 个逆序对，则转移为

$$f_{i,j}=\sum_{k=0}^{\min(i-1,j)} f_{i-1,j-k}$$

发现第二维是一个区间求和，用前缀和优化即可做到 $O(nk)$。

然后再看这道题。

概率显然可以转化为计数。设 $f_{i,j}$ 表示将 $1\sim i$ 填入排列，逆序对数在 $\operatorname{mod} \ k$ 意义下 为 $j$ 的方案数，转移为

$$f_{i,j}=\sum_{p=0}^{i-1}f_{i-1,(j-p)\operatorname{mod} \ k}$$

然后可以发现，第二维的转移依旧是连续区间，前缀和优化就做完了。

下面是具体的推导：

设 $d=(j-i+1) \operatorname{mod} \ k$。

当 $d\le j$ 时，$\forall \ x\in [d,j]$，$f_{i-1,x}$ 都能贡献到 $f_{i,j}$。

当 $j-i+1<0$ 时，即 $d<0$，此时在 $\operatorname{mod} \ k$ 后 $d>j$。

此时的贡献区间变为 $[0,j]$ 和 $[d,k-1]$，即 $\forall \ x\in [0,j]\cup [d,k-1]$，$f_{i-1,x}$ 都能贡献到 $f_{i,j}$。

复杂度 $O(nk)$。

题解区还给出了一个结论：当 $n\ge k$ 时，每种情况的概率均为 $\frac {1}{k}$。

我用了，因为这样就不用写滚动数组了，哎嘿。

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e3+10,mod=998244353;
int n,k;
int f[maxn][maxn],s[maxn][maxn];
inline int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
inline int Inv(int x){return qpow(x,mod-2);}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    if(n>=k){for(re int i=0;i<k;++i) cout<<Inv(k)<<' ';return 0;}
    int inv=1;
    for(re int i=1;i<=n;++i) inv=inv*i%mod;inv=Inv(inv);
    f[1][0]=s[1][0]=1;
    for(re int j=1;j<k;++j) s[1][j]=1;
    for(re int i=2;i<=n;++i){
        for(re int j=0;j<k;++j){
            int d=((j-i+1)%k+k)%k;
            if(d<=j){
                if(!d) f[i][j]=s[i-1][j];
                else f[i][j]=((s[i-1][j]-s[i-1][d-1])%mod+mod)%mod;
            }
            else{
                f[i][j]=s[i-1][j];
                if(!d) f[i][j]=(f[i][j]+s[i-1][k-1])%mod;
                else f[i][j]=(f[i][j]+((s[i-1][k-1]-s[i-1][d-1])%mod+mod)%mod)%mod;
            }
            if(!j) s[i][j]=f[i][j];
            else s[i][j]=(s[i][j-1]+f[i][j])%mod;
        }
    }
    for(re int i=0;i<k;++i) cout<<f[n][i]*inv%mod<<' ';
    return 0;
}

「Wdsr-3」令人感伤的红雨

好题，可惜只想出来了两个 $\log$ 的无脑做法，感觉正解很牛啊。

先讲讲我的无脑思路：

题目给的条件看起来非常复杂，但事实上并不复杂。

先看 $A(l,r)$。

可以发现，$A(l,r)$ 代表的含义就是区间 $[l,r]$ 中最靠右侧的最大值的下标。

然后是 $B(l,r)$。

先看前半部分。可以发现，在固定右端点 $i$ 时，随着左端点左移，$A(j,i)$ 是单调不增的。

所以 $\min_{j=1}^i A(j,i)$ 事实上就等于 $A(1,i)$。

然后又可以发现，在固定左端点时，随着右端点右移，$A(1,i)$ 是单调不减的。

所以 $\max_{i=l}^r A(1,i)$ 事实上就等于 $A(1,r)$。

然后看后半部分。

借助上面的结论，可以发现 $\max_{j=1}^i A(j,i)=i,\min_{i=l}^r i=l$。

所以 $B(l,r)=A(1,r)-l$。

最后是 $\Omega(l,r)$。

把我们得到的 $B(l,r)$ 带进去，发现需要求的就是 $\min_{i=l}^r \min_{j=i}^r |A(1,j)-i|$。

可以发现，只要存在 $A(1,j)$ 的取值在 $[l,r]$ 中，$\Omega(l,r)$ 的值就为 $0$。

而我们又知道，$A(1,j)\le j$ 且 $A(1,j)$ 随着 $j$ 的增大单调不减。

所以可以得到结论：若 $A(1,r)\ge l$，则 $\Omega(l,r)=0$，否则 $\Omega(l,r)=l-A(1,r)$。

那么现在的问题就是：如何维护 $A(1,i)$？

因为我很无脑，所以只想到了无脑做法。

可以发现，修改操作是前缀加。

设前缀加的区间为 $[1,x]$，那么这次操作可能影响的值为 $A(1,[x+1,n])$。

因为前缀加不会影响相对大小，所以对 $A(1,[1,x])$ 没有影响。

但是对 $[x+1,n]$ 来说，前缀加以后，可能会有 $[1,x]$ 中的某个数成为它们的前缀最大值。

因为前缀最大值单调不减，所以每次前缀加影响的都是 $[x+1,n]$ 的一段前缀。

因为有单调性，所以可以二分找出。

那么我们要实现的操作有：

• 对原序列前缀加，求前缀最大值。
• 对 $A$ 序列区间推平，单点查询。

显然可以线段树，于是我们就做到了 $O(n\log^2 n)$。

二分还是有点细节的：因为 $A$ 的值为最靠右侧的最大值的下标，所以出现多个最大值时要找最右边那个，二分的时候要注意一下。

#include"bits/stdc++.h"
#define re register
#define int long long
#define max(a,b) (a<b?b:a)
using namespace std;
const int maxn=6e6+10;
int n,m;
int a[maxn],A[maxn]; 
struct node{
    int mx,id;
    inline node operator + (const node &a)const{
        if(mx==a.mx) return {mx,max(id,a.id)};
        else if(mx>a.mx) return {mx,id};
        else return a;
    }
};
struct tree1{
    int rt,segcnt;
    int ls[maxn<<1],rs[maxn<<1];
    node s[maxn<<1];
    int tag[maxn<<1];
    inline void up(int p){s[p]=s[ls[p]]+s[rs[p]];}
    inline void add(int p,int val){s[p].mx+=val,tag[p]+=val;}
    inline void down(int p){if(tag[p]) add(ls[p],tag[p]),add(rs[p],tag[p]),tag[p]=0;}
    inline void build(int l,int r,int &p){
        p=++segcnt;
        if(l==r){s[p].mx=a[l],s[p].id=l;return;}
        int mid=(l+r)>>1;
        build(l,mid,ls[p]),build(mid+1,r,rs[p]);
        up(p);
    }
    inline void update(int l,int r,int L,int R,int val,int p){
        if(l>=L&&r<=R){add(p,val);return;}
        int mid=(l+r)>>1;down(p);
        if(L<=mid) update(l,mid,L,R,val,ls[p]);
        if(R>mid) update(mid+1,r,L,R,val,rs[p]);
        up(p);
    }
    inline node query(int l,int r,int L,int R,int p){
        if(l>=L&&r<=R) return s[p];
        int mid=(l+r)>>1;down(p);
        if(R<=mid) return query(l,mid,L,R,ls[p]);
        if(L>mid) return query(mid+1,r,L,R,rs[p]);
        return query(l,mid,L,R,ls[p])+query(mid+1,r,L,R,rs[p]);
    }
}tr1;
struct tree2{
    int rt,segcnt;
    int ls[maxn<<1],rs[maxn<<1];
    int ans[maxn<<1],tag[maxn<<1];
    inline void add(int p,int val){ans[p]=val,tag[p]=val;}
    inline void down(int p){if(tag[p]) add(ls[p],tag[p]),add(rs[p],tag[p]),tag[p]=0;}
    inline void build(int l,int r,int &p){
        p=++segcnt;
        if(l==r){ans[p]=A[l];return;}
        int mid=(l+r)>>1;
        build(l,mid,ls[p]),build(mid+1,r,rs[p]);
    }
    inline void update(int l,int r,int L,int R,int val,int p){
        if(L>R) return;
        if(l>=L&&r<=R){add(p,val);return;}
        int mid=(l+r)>>1;down(p);
        if(L<=mid) update(l,mid,L,R,val,ls[p]);
        if(R>mid) update(mid+1,r,L,R,val,rs[p]);
    }
    inline int query(int l,int r,int pos,int p){
        if(l==r) return ans[p];
        int mid=(l+r)>>1;down(p);
        if(pos<=mid) return query(l,mid,pos,ls[p]);
        else return query(mid+1,r,pos,rs[p]);
    }
}tr2;
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1;i<=n;++i) cin>>a[i];
    int mx=0,id=0;
    for(re int i=1;i<=n;++i){
        if(mx<=a[i]) mx=a[i],id=i;
        A[i]=id;
    }
    tr1.build(1,n,tr1.rt),tr2.build(1,n,tr2.rt);
    for(re int i=1,op,x,y;i<=m;++i){
        cin>>op>>x>>y;
        if(op==1){
            tr1.update(1,n,1,x,y,tr1.rt);
            node res=tr1.query(1,n,1,x,tr1.rt);
            int l=x+1,r=n,mid,pos=n+1;
            //二分找到（第一个前缀最大值大于[1,x]中最大值的位置）或（前缀最大值等于[1,x]中最大值且最大值下标大于[1,x]中最大值下标的位置）
            while(l<=r){
                mid=(l+r)>>1;
                node tmp=tr1.query(1,n,1,mid,tr1.rt);
                if(tmp.mx==res.mx){
                    if(tmp.id>res.id) pos=mid,r=mid-1;
                    else l=mid+1;
                }
                else if(tmp.mx>res.mx) pos=mid,r=mid-1;
                else l=mid+1;
            }  
            tr2.update(1,n,x+1,pos-1,res.id,tr2.rt);
        }
        if(op==2){
            int pos=tr2.query(1,n,y,tr2.rt);
            if(pos>=x) cout<<0<<'\n';
            else cout<<x-pos<<'\n';
        }
    }
    return 0;
}

upd：昨天是不是降智了啊？

这凭啥要开两颗线段树，前缀加，查前缀最大值位置，第一颗线段树不是已经维护完了吗？

不过确实启发正解了。

复杂度 $O(n\log n)$，但因为常数巨大无法通过。

upd：学弟卡过去了，在这放个题解。

#include"bits/stdc++.h"
#define re register
#define int long long
#define max(a,b) (a<b?b:a)
using namespace std;
const int maxn=6e6+10;
int n,m;
int a[maxn],A[maxn]; 
struct node{
    int mx,id;
    inline node operator + (const node &a)const{
        if(mx==a.mx) return {mx,max(id,a.id)};
        else if(mx>a.mx) return {mx,id};
        else return a;
    }
};
struct tree1{
    int rt,segcnt;
    int ls[maxn<<1],rs[maxn<<1];
    node s[maxn<<1];
    int tag[maxn<<1];
    inline void up(int p){s[p]=s[ls[p]]+s[rs[p]];}
    inline void add(int p,int val){s[p].mx+=val,tag[p]+=val;}
    inline void down(int p){if(tag[p]) add(ls[p],tag[p]),add(rs[p],tag[p]),tag[p]=0;}
    inline void build(int l,int r,int &p){
        p=++segcnt;
        if(l==r){s[p].mx=a[l],s[p].id=l;return;}
        int mid=(l+r)>>1;
        build(l,mid,ls[p]),build(mid+1,r,rs[p]);
        up(p);
    }
    inline void update(int l,int r,int L,int R,int val,int p){
        if(l>=L&&r<=R){add(p,val);return;}
        int mid=(l+r)>>1;down(p);
        if(L<=mid) update(l,mid,L,R,val,ls[p]);
        if(R>mid) update(mid+1,r,L,R,val,rs[p]);
        up(p);
    }
    inline node query(int l,int r,int L,int R,int p){
        if(l>=L&&r<=R) return s[p];
        int mid=(l+r)>>1;down(p);
        if(R<=mid) return query(l,mid,L,R,ls[p]);
        if(L>mid) return query(mid+1,r,L,R,rs[p]);
        return query(l,mid,L,R,ls[p])+query(mid+1,r,L,R,rs[p]);
    }
}tr;
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1;i<=n;++i) cin>>a[i];
    int mx=0,id=0;
    for(re int i=1;i<=n;++i){
        if(mx<=a[i]) mx=a[i],id=i;
        A[i]=id;
    }
    tr.build(1,n,tr.rt);
    for(re int i=1,op,x,y;i<=m;++i){
        cin>>op>>x>>y;
        if(op==1) tr.update(1,n,1,x,y,tr.rt);
        if(op==2){
            int pos=tr.query(1,n,1,y,tr.rt).id;
            if(pos>=x) cout<<0<<'\n';
            else cout<<x-pos<<'\n';
        }
    }
    return 0;
}

以下是正解：

在看完题解以后发现我其实也想到这东西了，但是不知道咋做就放弃了。

刚才我们忽略了一个重要性质：每次前缀加的都是一个非负数。

我们将 $A$ 序列拿出来看，会发现，$A$ 中不同元素个数是单调不增的，且 $A$ 序列是单调不降的。

因为每次前缀加，事实上都是在把后面的一些答案合并到前面。

你可以理解为，一个答案 $x$ ，掌管着一段连续的 $A$，每次前缀加都会把后面一段连续的 $A$ 合并过来。

而且总合并次数事实上是 $O(n)$ 的。

我们可以使用并查集+链表实现这个合并。

设 $A$ 序列去重后得到的序列为 $b$，即前缀最大值位置的集合。

我们用一个并查集维护 $A$。初始时，$i$ 的父亲为 $A_i$。

然后我们用一个链表维护 $b$。$b_i$ 指向 $b_{i+1}$，边权为 $a_{b_{i+1}}-a_{b_i}$。

假设现在给 $[1,x]$ 加上 $y$，那么我们先把 $x$ 跳到父亲，然后将链表的边权 $-y$。

若边权 $<0$，说明需要合并到前面了，那么我们就顺着链表向后跳，然后向前合并，一直跳到无法合并位置。

查询答案时，直接跳到 $x$ 的父亲，得到的就是 $A(1,x)$。

复杂度 $O(n\log n)$。

感觉这个非常难说清，大家感受一下吧。

#include"bits/stdc++.h"
#define re register
#define int long long
#define max(a,b) (a<b?b:a)
using namespace std;
const int maxn=6e6+10;
int n,m;
int a[maxn],A[maxn],nxt[maxn],c[maxn]; 
inline int find(int x){if(x!=A[x]) A[x]=find(A[x]);return A[x];}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1;i<=n;++i) cin>>a[i],nxt[i]=n+1,c[i]=-1;
    int mx=0,id=0;
    for(re int i=1;i<=n;++i){
        if(mx<=a[i]){
            nxt[id]=i,c[id]=a[i]-mx;
            mx=a[i],id=i;
        }
        A[i]=id;
    }
    for(re int i=1,op,x,y,tmp,del;i<=m;++i){
        cin>>op>>x>>y;
        if(op==1){
            tmp=find(x);
            c[tmp]-=y;
            while(nxt[tmp]<n+1&&c[tmp]<0){
                del=nxt[tmp];
                c[tmp]+=c[del];
                nxt[tmp]=nxt[del];
                A[del]=tmp;
                nxt[del]=n+1;
                c[del]=-1;
            }
        }
        else cout<<max(0,x-find(y))<<'\n';
    }
    return 0;
}

[Cnoi2021] 符文破译

没想到对 KMP 的理解已经烂到这种程度了，看到这种题竟然都想不到。

因为我们要将 $S$ 拆分成若干 $T$ 的前缀且数量最少，所以贪心的让每一段长度越长越好。

所以第一个思路就是正着匹配过去，能匹配多长就匹配多长。

但是样例二就把这个思路给否定了：前面一段长的匹配可能导致后面无法匹配。

所以很自然的，想到倒过来匹配。

那么我们要做的就是：每次找到 $S$ 的一段最长后缀，使得其和 $T$ 的某个前缀匹配，然后把后缀删掉。

想了半天哈希怎么做，但仔细想一下，最长公共前后缀，这不是 KMP 吗？

所以把 $T$ 和 $S$ 拼起来，然后做一遍 KMP。

每次跳 border，直到跳到间隔符为止。

如果某个 border 长度为 $0$，说明无解。

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=2e7+10;
int n,m,ans;
int nxt[maxn];
string s,s1,s2;
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>s1>>s2;
    s=' '+s1+'#'+s2;n=s.length()-1;
    nxt[1]=0;
    for(re int i=2,j=0;i<=n;++i){
        while(j&&s[j+1]!=s[i]) j=nxt[j];
        if(s[j+1]==s[i]) ++j;
        nxt[i]=j;
    }
    int pos=n;
    while(s[pos]!='#'){
        if(!nxt[pos]){cout<<"Fake";return 0;}
        pos=pos-nxt[pos];
        ++ans;
    }
    cout<<ans;
    return 0;
}