C
计数 dp优化
对一个长度为n的排列跑单调栈，最后栈中剩下的元素个数为，
注意到一个排列增加一个元素，对剩余元素个数的影响时很好分析的，如果给一个长度n的排列增加一个元素n+1，只有在n+1插入到排列的结尾时，单调栈中剩余元素个数才会增加，其余位置元素个数都不变。
增加一个元素，变化可以求，很适合dp。考虑
表示，长度为j的排列，跑单调栈的剩余元素个数为i的方案数。这可以递推
，
光有这个转移还不够，我们要求的是。而这个转移的状态数是
的，肯定超时。要想办法得到一个转移只有
个状态的dp，也就是状态定义是
，然后可以
地转移这个
。
但是这里还带个太难转移了，考虑增加一些状态来辅助
也就是可以分别维护，然后递推
时可以用
,递推
可以用
具体就是
推时会用到
，也就是一行的系数和，可以手玩，或者发现这个转移就是第一类斯特林数，得到一行的和就是
D
隔板法 转化
最后一个条件手玩，可以发现等价于，如果把矩阵看成列前缀和，原数组每列单调。第二个条件又告诉我们这个前缀和数组也是每行单调的。
所以可以看成，有一个矩阵，先每列从下往上前缀和，再每行从左往右前缀和，得到了这个矩阵，所以
就是矩阵所有元素的和。又有
，也即是二位前缀和之前的这个矩阵，所有元素的和加起来不超过
这是经典问题，不是严格等于，而是不超过。应用隔板法结论，相当于把不超过个球放到
个盒子里，可以空盒，答案是
E
分块
在原序列上修改，给出原序列的一个排列，对这个排列进行区间询问。
区间询问先想到的线段树，但是这题区间维护的信息不好合并。这种时候一个经典的思路是，不好合并就不合并考，考虑暴力一点的数据结构，往往就是分块。
分块也能维护区间修改区间查询，但是不会合并两个块的信息，而是每个块都单独维护，最后遍历所有块，累加答案。这样每个块内的信息就很好维护，因为不用考虑合并了。
本题信息不好合并，考虑分块。但特殊之处在于，查询和修改不是在一个序列，如果我麽能只对原序列分块，可以处理查询，但查询不好做，或者只对排列分块，可以处理询问，但修改不好做。所以考虑对原序列和排列都分块。而这样的话我们需要知道原序列的块对排列的块的贡献，考虑建立一个映射，记录原序列里第
个块，有多少个元素在排列第
个块内。
接下来考虑分块的一般思路，每个块有两种标签：和标签，整体加标签。考虑四种贡献：修改时散点对查询时散点，修改时散点对查询时整块，修改时整块对查询时散点，修改时整块对查询时整块。
前三种，涉及散点，其实都是暴力，枚举散点，都枚举了，一般直接改/查数组就行。还是和一般的分块一样，散点对散点，直接单点修改原数组，散点对整块，给散点所在的原数组的和标签加上，整块对散点，查询散点所在的整块，检查整块的整体加标签。
最后整块对整块，需要考虑块对块的贡献。假设询问的块编号在区间，那么枚举原序列的所有块，第
个块，对于查询的贡献是
，可以对映射数组做个前缀和，然后查询贡献，乘上第
个块的整体加标签。
难点在想到两个分块，以及映射的实现。这个代码里单点修数组是，整体加标签是
，块的和标签是
int p[N],f[1000][1000];
vi pos[N];
struct block {
int a[N], b[N], add[N];
int sz;
void init(int x) {
sz = x;
}
int ask(int l, int r) {
int res = 0;
int id1 = l / sz, id2 = r / sz;
if (id1 == id2) {
rep(i, l, r) {
res += a[p[i]] + add[p[i]/sz];
}
} else {
bool flag=0;
if (l % sz == 0) {
flag=1;
} else {
while (l / sz == id1) {
res += a[p[l]] + add[p[l]/sz];
l++;
}
}
while (r / sz == id2) {
res += a[p[r]] + add[p[r]/sz];
r--;
}
int lo=id1+1-flag,hi=id2-1;
rep(i,0,sz) {
int t=f[i][hi];
if(lo!=0)t-=f[i][lo-1];
res += add[i]*t;
}
rep(i, lo, hi){
res += b[i];
}
}
return res;
}
void upd(int l, int r, int v) {
int id1 = l / sz, id2 = r / sz;
if (id1 == id2) {
rep(i, l, r) {
a[i] += v;
for(int j:pos[i]){
b[j]+=v;
}
}
} else {
bool flag=0;
if (l % sz == 0) {
flag=1;
} else {
while (l / sz == id1) {
a[l] += v;
for(int i:pos[l]){
b[i]+=v;
}
l++;
}
}
while (r / sz == id2) {
a[r] += v;
for(int i:pos[r]){
b[i]+=v;
}
r--;
}
rep(i, id1 + 1-flag, id2 - 1) {
add[i] += v;
};
}
}
} b;
void solve() {
int n,m;
cin >> n>>m;
int sz = sqrt(n);
b.init(sz);
rep(i,0,n-1){
cin>>p[i];
p[i]--;
pos[p[i]].push_back(i/sz);
f[p[i]/sz][i/sz]++;
}
rep(i,0,sz){
rep(j,1,sz){
f[i][j]+=f[i][j-1];
}
}
int last=0;
rep(i, 1, m) {
int op, l, r, v;
cin >> op >> l >> r;
l^=last,r^=last;
if (op == 2) {
// cout<<l<<' '<<r<<'\n';
int ans = b.ask(l - 1, r - 1);
cout<<ans<<'\n';
last=ans;
} else {
cin>>v;
v^=last;
// cout<<l<<' '<<r<<' '<<v<<'\n';
b.upd(l - 1, r - 1, v);
}
}
}
G
广义矩阵乘 动态
每个人朝左或者朝右，每一秒相对的两个人都会转身，问多少秒之后所有人会稳定下来。带修改，输出每次修改后的答案。
原问题可以dp，带修改，显然是个动态dp。把原问题的转移写成一个矩阵，用线段树来维护修改后的结果变化。
先来看这个dp本身。首先相遇转身这个东西，一个经典转化是可以看成两个人擦肩而过，穿过对方。那么这个过程实际上就是，所有可以看成不懂的障碍物，所有
可以看成人，每个人都要走过他左侧所有的障碍物。但需要等它左侧的人先走，左侧的人走了之后的下一秒，这个人才能走。
可以手玩来理解这个视角
，可以按原始定义看成左边两个人都转身了，也可以按我们转化后的定义，看成第一个
往左走了一步，跨过了这个
障碍物
转化后的就好想了，对于一个人，开始走的时间比左侧第一个人要晚一秒，所以总的用时要比左边这个人多一秒，也就是如果一个人
左侧紧贴着另一个人
，转移就是
如果左侧是一段障碍物，需要先跨过这段障碍物，才会遇到一个人，那么有可能走完这段障碍物后，原本左边的人已经走完了，瓶颈在于走这段障碍物的时间，也可能这段障碍物很短，走完了左侧第一个人还在排队，还没启动，那么需要先等左边的人先动，等价于紧贴一个人的情况，转移则为，
是这段障碍物左侧第一个人的位置，
是这段障碍物的长度
这个转移在实现上有一种简单的方式，就是让障碍物也可以有值，但因为不是人，答案显然不会有变化，直接继承上一轮的答案，这样就不用找
了，一个人可以直接从左侧障碍物转移。
总结一下就是，如果，
，不论
，如果
,
。
数组转移同时，需要维护
左侧连续障碍物长度
，这很好转移。
有了一个转移方程，但我们发现这个方程里带，不只有线性组合。不能直接用矩阵乘法表示转移。
但是呢，还是只有两种运算，加法，取最大值，且先进行一种，再进行另一种，并且这两种运算都有交换律，结合律，分配律。那么其实仍然可以用类似矩阵的思路来，把矩阵乘法的加法和乘法，换成加法和取最大。这相当于拓展了矩阵乘法的定义，所以也叫广义矩阵乘。
用这个拓展之后的矩阵，就可以表示这个转移方程了，然后使用一般的线段树维护矩阵乘法即可。注意我们需要同时维护两个状态，，所以矩阵是
的，矩阵可以右乘状态向量，也可以左乘，区别是矩阵需要转置一下。并且左乘的话，向量是列向量，右乘的话，向量是行向量
这里采用右乘状态向量，转移矩阵则为
并且状态向量是行向量。手玩一下转移的话，考虑的
转移，把向量第一行（就是向量本身）和矩阵第一列，先每个位置加起来，得到
，然后再把这些结果取
，作为第一行第一列也就是
的答案，也就实现了
最后需要注意，矩阵有点卡常，最好用数组或者array来实现，不要用vector，以及在这次比赛的卡常过程中我发现，clang比gcc要快
typedef array<array<int,2>,2> Matrix;
Matrix L={
{
{1,-M1},
{0,0}
}
};
Matrix R={
{
{0,-M1},
{-M1,1}
}
};
Matrix g[2]={L,R};
void print_Matrix(const Matrix &a){
int n=a.size();
int m=a[0].size();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<a[i][j]<<' ';
}
cout<<'\n';
}
}
// 矩阵乘法
Matrix multiply(const Matrix &A, const Matrix &B, long long MOD=M2)
{
int n = A.size();
int m = B[0].size();
int k = B.size();
Matrix C;
rep(i,0,n-1){
rep(j,0,m-1){
C[i][j]=-1e9;
}
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
for (int l = 0; l < k; ++l)
{
C[i][j] = max(C[i][j] , A[i][l] + B[l][j] );
}
}
}
return C;
}
struct Tree
{
#define ls u << 1
#define rs u << 1 | 1
struct Node
{
int l, r,val;
Matrix m;
Node operator+(const Node &o)
{
Node res;
res.l = l;
res.r = o.r;
res.m=multiply(m,o.m);
return res;
}
} tr[N << 2];
void pushup(int u)
{
tr[u] = tr[ls] + tr[rs];
}
void build(int u, int l, int r,string &s)
{
tr[u].l=l;
tr[u].r=r;
if(s[l]=='L')tr[u].val=0;
else tr[u].val=1;
tr[u].m=g[tr[u].val];
if (l == r)
return;
int mid = (l + r) >> 1;
build(ls, l, mid,s);
build(rs, mid + 1, r,s);
pushup(u);
}
void modify(int u, int idx)
{
if (tr[u].l == tr[u].r)
{
tr[u].val ^=1;
tr[u].m=g[tr[u].val];
return;
}
else
{
int mid = (tr[u].l + tr[u].r) >> 1;
if (mid >= idx)
modify(ls, idx);
else
modify(rs, idx);
pushup(u);
}
}
Node query(int u, int l, int r)
{
if (l <= tr[u].l && tr[u].r <= r)
return tr[u];
int mid = (tr[u].l + tr[u].r) >> 1;
if (r <= mid)
return query(ls, l, r);
if (l > mid)
return query(rs, l, r);
return query(ls, l, r) + query(rs, l, r);;
}
} t;
void solve()
{
int n,q;
cin>>n>>q;
string s;
cin>>s;
s=' '+s;
t.build(1,1,n,s);
set<int>rpos;
rep(i,1,n){
if(s[i]=='R'){
rpos.insert(i);
}
}
rep(i,1,q){
int x;
cin>>x;
if(s[x]=='L'){
s[x]='R';
rpos.insert(x);
t.modify(1,x);
}
else{
s[x]='L';
rpos.erase(x);
t.modify(1,x);
}
if(!rpos.size()){
cout<<0<<'\n';
}
else{
int first_r=*rpos.begin();
auto res=t.query(1,first_r,n);
Matrix f0={{0,0}};
Matrix ans=multiply(f0,res.m);
cout<<ans[0][0]<<'\n';
}
}
}
J
树上独立集 容斥 树上背包
每次随机删一个点，及其相邻边，直到所有边都被删，问操作次数的期望
期望，可以用定义，计算出操作次数为的概率。这个概率可以看成，生成一个删除序列，按这个序列从左往右删除，直到满足要求，不能删了，执行次数为
次，所有这样的序列个数，除以序列总数，就是操作次数为
的概率。总方案数就是
，好求，所以问题是，求删除次数为
的删除序列个数
每次删一个点，直到所有边都被删，这个条件可以转化一下：每个边至少有一个点被删了，所以最后剩下的点里，没有相邻的。也就是是一个独立集。
如果知道剩余的这个独立集的，其大小为，那么删除次数就是
。并且可以得到最后剩余这些点的方案数，也就是我们指定一个删除序列，把这
个点放在最后
个，这样的方案数是
。如果还能求出大小为
的独立集个数
，就能得到所有最后剩余
个点的方案数，
但注意这样求出来删除序列，实际上可能重复，这样只能保证，求出来的是删除次数小于等于的删除序列个数，因为最后k个肯定是个独立集，最多删到还剩
个就会停下，但不保证最后
个是不是独立集，可能也是。
所以想要得到删除次数严格等于的方案数，需要把
差分一下。然后计算期望
最后的关键部分是，求出所有，也就是所有大小的树上独立集的个数
如果只是求树上独立集个数，这是树形简单问题，
表示当前点选不选，当前子树内的独立集个数。但这里还需要求不同大小的独立集个数，增加一个维度
记录
子树内，大小为
的独立集个数，
点选或不选
转移时需要从每个子树里选一些点，最后组成整个数的大小，这其实是个树上背包，不谈，注意树上背包经典问题，控制枚举上界，保证复杂度即可
int dp[5050][5050][2],fac[N];
void solve()
{
int n;
cin>>n;
fac[0]=1;
rep(i,1,n){
fac[i]=fac[i-1]*i%M2;
}
vvi g(n+1);
rep(i,1,n-1){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
auto &&dfs=[&](auto&&dfs,int u,int f)->int{
int sz=1;
dp[u][1][1]=1;
dp[u][0][0]=1;
for(int v:g[u]){
if(v==f)continue;
int sz1=dfs(dfs,v,u);
rep1(i,sz,0){
rep1(j,sz1,1){
dp[u][i+j][1]=(dp[u][i+j][1]+dp[u][i][1]*dp[v][j][0]%M2)%M2;
dp[u][i+j][0]=(dp[u][i+j][0]+dp[u][i][0]*(dp[v][j][0]+dp[v][j][1])%M2)%M2;
}
}
sz+=sz1;
}
return sz;
};
dfs(dfs,1,-1);
vi f(n+1);
rep(i,0,n){
f[i]=(dp[1][i][0]+dp[1][i][1])%M2;
f[i]=f[i]*fac[i]%M2*fac[n-i]%M2;
// cout<<dp[1][i][1]<<' ';
}
int ans=0;
rep(i,0,n-1){
ans=(ans+(n-i)*(f[i]-f[i+1]+M2))%M2;
}
cout<<ans*inv(fac[n],M2)%M2;
}
K
数论 区间同余
选一个区间加，问整个序列的
最大值？
如果整个序列都相同，可以无穷大，加完
也无穷大
如果给整个序列加，加完之后，那整个序列加之前，一定是模
同余的。于是问题转化成要找到一个最大的
，
模
同余
不妨设余数是，那么所有
都可以写成
，那么做个差分，就把
都减掉了，剩余是
，也就是每个数都是
的倍数，现在要找到最大的
，直接让所有数求
即可，这样就能找到，最大的，每个数都是他的倍数的
。
如果不加整个序列，至少有一个前缀，或一个后缀没被加。那没被加的这部分没变，直接被用来计算最后的，所以最后的
一定是这段前缀/后缀的
的因子。
可以枚举的因子
，然后逐个检查是否可能是最终答案，是最终答案的条件是：最多只有一段子区间，模
不为0，且这一段的余数相同，这样我们对这一段加上，可以让他们模
余0，剩余位置本来就余0，整体就模
余0了。
但这样还是太慢，再注意到前缀的，一定也是
的因子，因为
是个取交集的过程。准确的说，所有前缀可能出现的
，就是
的所有因子。所以我们不用枚举前缀，求
，再分解这个
的因子，直接枚举
的因子即可。
这样是考虑了所有不加前缀的区间加的情况，还可能是不加后缀，也同理，再枚举的因子即可。
检查最多只有一段模不为0，且这一段余数相同，可以用个状态机来做
#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 1E5 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;
bool check(int g, vector<int> &a) {
int n = (int)a.size() - 1;
int state = 0, tmp = 0;
for (int i = 1; i <= n; i++) {
int t = a[i] % g;
if (state == 0) {
if (t != 0) {
state = 1;
tmp = t;
}
} else if (state == 1) {
if (t == 0)
state = 2;
else if (t != tmp)
return false;
} else {
if (t != 0) return false;
}
}
return true;
}
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
bool same = true;
for (int i = 1; i <= n; i++) {
if (a[i] != a[1]) same = false;
}
if (same) {
cout << 0 << "\n";
return;
}
vector<int> b(n);
for (int i = 1; i <= n - 1; i++) {
b[i] = abs(a[i+1] - a[i]);
}
int ans = b[1];
for (int i = 1; i <= n - 1; i++) {
ans = gcd(ans, b[i]);
}
unordered_set<int> vis;
int num = a[1];
for (int i = 1; i * i <= num; i++) {
if (num % i != 0) continue;
if (!vis.count(i)) {
bool ok = check(i, a);
if (ok) ans = max(ans, i);
vis.insert(i);
}
if (!vis.count(num / i)) {
bool ok = check(num / i, a);
if (ok) ans = max(ans, num / i);
vis.insert(num / i);
}
}
num = a[n];
for (int i = 1; i * i <= num; i++) {
if (num % i != 0) continue;
if (!vis.count(i)) {
bool ok = check(i, a);
if (ok) ans = max(ans, i);
vis.insert(i);
}
if (!vis.count(num / i)) {
bool ok = check(num / i, a);
if (ok) ans = max(ans, num / i);
vis.insert(num / i);
}
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T = 1;
cin >> T;
for (int ttt = 1; ttt <= T; ++ttt) {
solve();
}
return 0;
}
K
贪心 树状数组
直接想排序比较难想。一个更显然的切入点是证明里的这个思路，考虑字典序最小的显然是开头个左括号，然后每次增加一个区间，考虑移动括号，满足这个区间的约束，并且尽可能保证字典序最小。
问题就是按什么顺序处理这些区间。如果按照左端点升序，可能在处理完了一个区间之后，下一个区间和这个区间有交集，那么与其从前缀里取一个，不如把上一个区间的开头左括号，移动到这区间开头。但显然这样做很麻烦。实际上是因为后效性，考虑新的区间时，可能会动前面已经分好的，还需要知道前面区间都在哪。
当每个元素都是往后有一段长度的区间时，出现后效性是个常见的问题。这时就可以考虑倒序处理。在这里也就是根据左端点降序枚举区间，先检查当前区间范围内，是否有左括号，如果有就不用安排新的，否则在左端点安排一个。这相当于区间查，单点修，可以树状数组/线段树
最后按这个方式填完了，剩余位置填右括号。检查是否符合合法括号的要求，不满足则无解，因为这已经是在满足区间约束的前提下，字典序最小的方案了（如果认为左括号字典序小于右括号，字典序越小的方案，根据前缀和转化，越可能满足前缀和始终非负的约束，越可能是合法括号串，所以如果这个字典序最小的方案都不是合法括号串，其他的更不可能是了）。如果填的过程中左括号就不够了，也无解。
#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;
void solve() {
int n,m;
cin>>n>>m;
int tot=n;
vector<vector<int>>a;
vector<int>ans(2*n+10);
vector<int>t(2*n+10);
auto ask=[&](int x)->int{
int res=0;
while(x>0){
res+=t[x];
x-=x&(-x);
}
return res;
};
auto add=[&](int x,int v)->void{
while(x<=2*n){
t[x]+=v;
x+=x&(-x);
}
};
for(int i=0;i<m;i++){
int l,r;
cin>>l>>r;
a.push_back({l,r});
}
sort(a.begin(),a.end(),[&](auto &x,auto &y){
return x[0]>y[0];
});
for(auto &p:a){
int l=p[0],r=p[1];
int sum=ask(r)-ask(l-1);
if(sum)continue;
if(tot){
tot--;
add(l,1);
ans[l]=1;
}
else{
cout<<-1<<'\n';
return;
}
}
int pos=1;
while(tot){
if(ans[pos]){
pos++;
continue;
}
ans[pos]=1;
pos++;
tot--;
}
int sum=0;
for(int i=1;i<=2*n;i++){
if(ans[i])sum++;
else sum--;
if(sum<0){
cout<<-1<<'\n';
return;
}
}
for(int i=1;i<=2*n;i++){
if(ans[i])cout<<'(';
else cout<<')';
}
cout<<'\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T = 1; cin >> T;
for (int ttt = 1; ttt <= T; ++ttt) {
solve();
}
return 0;
}
京公网安备 11010502036488号