2023.01.17 模拟赛小结
目录更好的阅读体验戳此进入
赛时思路
T1
LG-P8280 「MCOI-08」Photoelectric Effect。
有一棵 \(n\)（\(1\le n\le 10^5\)）个点的树以及 \(k\)（\(2\le k\le 5\)）个颜色，根节点为 \(1\)。同时，给定一个颜色合并函数 \(a\otimes b\)，满足当 \(1\le a,b\le k\)，有 \(1\le a\otimes b\le k\)。
请问有多少个方案对所有点染色，使得当点对 \(u,v\) 之间没有祖先关系，有：
- \(u\) 和 \(v\) 最近公共祖先的颜色为点 \(u\) 的颜色和点 \(v\) 的颜色之并。
答案对 \(10^9+7\) 取模。
一个较为显然的 树形DP + 状压DP，复杂度卡的比较满，细节巨多，但是思路较为显然，赛时写了 $ 2h $，大样例也过了，然后最后 LemonLime 上 whs 造的数据过了 $ 90\texttt{pts} $，但是 Luogu 上几乎全 WA 了，最后找了一下才发现判断叶子节点时 !head[p]->nxt 把根也当成叶子了，也就是如果根只有一个子树那就会寄掉。
然后还有个问题就是 Luogu 上必须把边数开到 $ 2e6 $，开到 $ 1e6 $ 都不行，这也是一个亟待解决的问题。
当然这里的代码是赛时不太正确的，AC Code 参考下文。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MOD (ll)(1e9 + 7)
#define S(name, idx) ((name) & (1 << ((idx) - 1)))
template < typename T = int >
inline T read(void);
struct Edge{
Edge* nxt;
int to;
OPNEW;
}ed[210000];
ROPNEW;
Edge* head[210000];
int N, K;
int Smx;
int opt[10][10];
struct Node{int S; int col;};
basic_string < Node > legal[40];
ll dp[110000][40][6];
ll merg[40][6];
void Clear(void){
for(int i = 0; i <= Smx; ++i)legal[i].clear();
for(int i = 0; i <= N; ++i)head[i] = npt;
for(int i = 0; i <= N; ++i)for(int S = 0; S <= Smx; ++S)for(int k = 1; k <= K; ++k)dp[i][S][k] = 0;
}
void TreeDP(int p = 1, int fa = 0){
for(auto i = head[p]; i; i = i->nxt)if(SON != fa)TreeDP(SON, p);
if(!head[p]->nxt){for(int i = 0; i < K; ++i)dp[p][1 << i][i + 1] = 1; return;}
memset(merg, 0, sizeof merg);
bool isbeg(true);
for(auto i = head[p]; i; i = i->nxt){
if(SON == fa)continue;
if(isbeg){
isbeg = false;
for(int S = 1; S <= Smx; ++S)for(int j = 1; j <= K; ++j)for(int k = 1; k <= K; ++k)(merg[S][j] += dp[SON][S][k]) %= MOD;
// printf("p is %d, after merge, merge is : \n", p);
// for(int S = 1; S <= Smx; ++S)for(int i = 1; i <= K; ++i)
// cout << "merg[" << i << "][" << bitset < 5 >(S) << "] = " << merg[S][i] << endl;
continue;
}
ll lst[40][6];
for(int S = 0; S <= Smx; ++S)for(int j = 1; j <= K; ++j)lst[S][j] = merg[S][j], merg[S][j] = 0;
ll sum[40]; memset(sum, 0, sizeof sum);
for(int S = 1; S <= Smx; ++S)for(int j = 1; j <= K; ++j)(sum[S] += dp[SON][S][j]) %= MOD;
for(int S1 = 1; S1 <= Smx; ++S1)
for(auto S2 : legal[S1])
(merg[S1 | S2.S][S2.col] += lst[S1][S2.col] * sum[S2.S] % MOD) %= MOD;
// printf("p is %d, after merge, merge is : \n", p);
// for(int S = 1; S <= Smx; ++S)for(int i = 1; i <= K; ++i)
// cout << "merg[" << i << "][" << bitset < 5 >(S) << "] = " << merg[S][i] << endl;
}
for(int S = 1; S <= Smx; ++S)
for(int i = 1; i <= K; ++i)
(dp[p][S | (1 << (i - 1))][i] += merg[S][i]) %= MOD;
}
int main(){
freopen("color.in", "r", stdin);
freopen("color.out", "w", stdout);
int T = read();
while(T--){
Clear();
N = read(), K = read();
Smx = (1 << K) - 1;
for(int i = 1; i <= K; ++i)for(int j = 1; j <= K; ++j)opt[i][j] = read();
for(int i = 2; i <= N; ++i){
int s = i, t = read();
head[s] = new Edge{head[s], t};
head[t] = new Edge{head[t], s};
}
for(int S1 = Smx; S1; S1 = (S1 - 1) & Smx)
for(int S2 = Smx; S2; S2 = (S2 - 1) & Smx){
int cur(-1);
bool flag(true);
for(int i = 1; i <= K; ++i){
if(!flag)break;
for(int j = 1; j <= K; ++j){
if(!flag)break;
if(S(S1, i) && S(S2, j)){
if(opt[i][j] != opt[j][i]){flag = false; break;}
if(!~cur)cur = opt[i][j];
else if(opt[i][j] != cur)flag = false;
}
}
}if(flag)legal[S1] += Node{S2, cur};
}
// for(int S = 1; S <= Smx; ++S)for(auto S2 : legal[S]){
// cout << bitset < 5 >(S) << "with" << bitset < 5 >(S2.S) << " col is" << S2.col << endl;
// }
TreeDP();
// for(int i = 1; i <= N; ++i)for(int S = 1; S <= Smx; ++S)for(int j = 1; j <= K; ++j)
// cout << "dp[" << i << "][" << j << "][" << bitset < 5 >(S) << "] = " << dp[i][S][j] << endl;
ll ans(0);
for(int S = 1; S <= Smx; ++S)for(int i = 1; i <= K; ++i)(ans += dp[1][S][i]) %= MOD;
printf("%lld\n", ans);
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
/*
2
5 2
1 2
2 1
1 2 1 4
5 2
1 2
1 1
1 2 1 4
*/
T2
给定 $ n $ 个点的树，存在点权 $ w_i \(，独立询问每次可能为单点修改点权，可能给出两点，\) A $ 在树上两点最短路径上选择两个点 $ x, y $ 最大化 $ w_x \bmod{w_y} $，后者在树上选择非 $ x, y $ 的两点同样最大化上式，对于每次询问求出 $ A $ 最大的值，并求出此时 $ B $ 最大的值，$ A $ 无法选择则输出 -1。
写了篇题解，内容就放在下文了，错的点是没有考虑到应该维护前 $ 5 $ 大，只维护了 $ 4 $，且常数过大，然后赛时被卡到了 $ 20\texttt{pts} $。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template < typename T = int >
inline T read(void);
struct Edge{
Edge* nxt;
int to;
OPNEW;
}ed[210000];
ROPNEW;
Edge* head[110000];
int N, Q;
ll w[110000];
int dep[110000], dfn[110000], hson[110000], siz[110000], ffa[110000], tp[110000], idx[110000];
void dfs_pre(int p = 1, int fa = 0){
dep[p] = dep[fa] + 1;
siz[p] = 1;
ffa[p] = fa;
for(auto i = head[p]; i; i = i->nxt){
if(SON == fa)continue;
dfs_pre(SON, p);
siz[p] += siz[SON];
if(siz[hson[p]] < siz[SON])hson[p] = SON;
}
}
void dfs_make(int p = 1, int top = 1){
tp[p] = top;
static int cdfn(0);
dfn[p] = ++cdfn;
idx[cdfn] = p;
if(hson[p])dfs_make(hson[p], top);
for(auto i = head[p]; i; i = i->nxt)
if(SON != ffa[p] && SON != hson[p])
dfs_make(SON, SON);
}
struct Node{
ll v[5], vu[5]; //v_max_with_2, v_unique
Node(void){memset(v, 0, sizeof v), memset(vu, 0, sizeof vu);}
friend Node operator + (const Node &a, const Node &b){
Node ret;
basic_string < ll > values;
for(int i = 1; i <= 4; ++i){
if(a.v[i])values += a.v[i];
if(b.v[i])values += b.v[i];
}sort(values.begin(), values.end(), greater < ll >());
for(auto it = values.begin(); it != values.end() && next(it) != values.end() && next(it, 2) != values.end();)
if(*it == *next(it) && *next(it) == *next(it, 2))it = values.erase(it);
else advance(it, 1);
for(int i = 1; i <= 4; ++i)
ret.v[i] = (int)values.size() >= i ? values.at(i - 1) : 0;
values.clear();
for(int i = 1; i <= 4; ++i){
if(a.vu[i])values += a.vu[i];
if(b.vu[i])values += b.vu[i];
}sort(values.begin(), values.end(), greater < ll >());
values.erase(unique(values.begin(), values.end()), values.end());
for(int i = 1; i <= 4; ++i)
ret.vu[i] = (int)values.size() >= i ? values.at(i - 1) : 0;
return ret;
}
};
class SegTree{
private:
Node mx[110000 << 2];
#define LS (p << 1)
#define RS (LS | 1)
#define MID ((gl + gr) >> 1)
public:
void Pushup(int p){
mx[p] = mx[LS] + mx[RS];
}
void Build(int p = 1, int gl = 1, int gr = N){
if(gl == gr)return mx[p].v[1] = mx[p].vu[1] = w[idx[gl = gr]], void();
Build(LS, gl, MID), Build(RS, MID + 1, gr);
Pushup(p);
}
void Modify(int id, int v, int p = 1, int gl = 1, int gr = N){//modify dfn////////////////////////////////
if(gl == gr)return mx[p].v[1] += v, mx[p].vu[1] += v, void();
if(id <= MID)Modify(id, v, LS, gl, MID);
else Modify(id, v, RS, MID + 1, gr);
Pushup(p);
}
Node Query(int l, int r, int p = 1, int gl = 1, int gr = N){
// printf("Querying l = %d, r = %d\n", l, r);
if(l <= gl && gr <= r)return mx[p];
if(gr < l || r < gl)return Node();
return Query(l, r, LS, gl, MID) + Query(l, r, RS, MID + 1, gr);
}
}st;
void Make(int s, int t){
Node cur;
while(tp[s] != tp[t]){
if(dep[tp[s]] < dep[tp[t]])swap(s, t);
cur = cur + st.Query(dfn[tp[s]], dfn[s]);
s = ffa[tp[s]];
}if(dep[s] < dep[t])swap(s, t);
cur = cur + st.Query(dfn[t], dfn[s]);
if(!cur.vu[1] || !cur.vu[2]){printf("-1\n"); return;}
Node ret = st.Query(1, N);
basic_string < ll > tmp;
for(int i = 1; i <= 4; ++i)if(ret.v[i])tmp += ret.v[i];
for(int i = 1; i <= 2; ++i)
if(find(tmp.begin(), tmp.end(), cur.vu[i]) != tmp.end())
tmp.erase(find(tmp.begin(), tmp.end(), cur.vu[i]));
if((int)tmp.size() < 2 || ((int)tmp.size() == 2 && tmp.at(0) == tmp.at(1))){printf("-1\n"); return;}
printf("%lld %lld\n", cur.vu[2], tmp.at(0) == tmp.at(1) ? tmp.at(2) : tmp.at(1));
// for(int i = 1; i <= 4; ++i)printf("mxchain mxvu[%d] = %lld\n", i, cur.vu[i]);
// for(int i = 1; i <= 4; ++i)printf("mxtree mxv[%d] = %lld\n", i, ret.v[i]);
}
int main(){
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
N = read();
for(int i = 1; i <= N - 1; ++i){
int s = read(), t = read();
head[s] = new Edge{head[s], t};
head[t] = new Edge{head[t], s};
}dfs_pre(), dfs_make();
for(int i = 1; i <= N; ++i)w[i] = read();
st.Build();
Q = read();
while(Q--){
int opt = read(), x = read(), y = read();
if(opt == 0)st.Modify(dfn[x], y);
else Make(x, y);
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
/*
7
1 2
2 3
2 4
1 5
5 6
5 7
5 4 3 2 1 4 3
6
1 3 4
1 2 5
1 2 1
0 2 1
1 2 5
1 2 1
*/
T3
给定一个 \(n\) 个数的序列 \(a\) 和一个数 \(k\)，定义一个 子区间 \([l,r]\) 是好的，当且仅当这个区间内存在一个 子序列 满足：
-
包含 \(a_l\) 和 \(a_r\)
-
任意相邻两个数差的绝对值不超过 \(k\)
请求出所有合法的子区间数量。多组数据，\(1\le \sum n\le 5\times 10^5,\ 0\le k\le 10^5,\ 1\le a_i\le 10^5\)。
不会，跳！
T4
给定 $ n $ 个区间 $ [x_i, y_i] $，保证所有区间均不同。令 $ f(l, r) $ 表示从 $ n $ 个区间中选择偶数个区间使得其求并集后恰为 $ [l, r] $ 的方案数，令 $ g(l, r) $ 表示从 $ n $ 个区间中选择奇数个区间使得其求并集后恰为 $ [l, r] $ 的方案数。给定 $ q $ 组询问 $ [l_i, r_i] $，输出 $ f(l_i, r_i) - g(l_i, r_i) $，对 $ 998244353 $ 取模。
赛时没想出来，确实是一道人类智慧性质题，很有 AGC 的感觉，赛时糊的暴力也挂了。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MOD (998244353ll)
template < typename T = int >
inline T read(void);
struct Range{int l, r;};
Range R[11];
int N, Q;
int main(){
freopen("segment.in", "r", stdin);
freopen("segment.out", "w", stdout);
N = read(), Q = read();
for(int i = 1; i <= N; ++i)R[i].l = read(), R[i].r = read();
sort(R + 1, R + N + 1, [](const Range &a, const Range &b)->bool{return a.l < b.l;});
int Smx = (1 << N) - 1;
while(Q--){
int l = read(), r = read();
ll F(0), G(0);
for(int S = Smx; S; S = (S - 1) & Smx){
int curl(-1), curr(-1);
bool flag(true);
for(int i = 0; i < N; ++i){
if(S & (1 << i)){
if(!~curl)curl = R[i + 1].l;
if(!~curr)curr = R[i + 1].r;
else{
if(R[i + 1].l > curr)flag = false;
else curr = R[i + 1].r;
}
}
}
if(flag && curl == l && curr == r){
if(__builtin_popcount(S) & 1)++G;
else ++F;
}
}
printf("%lld\n", ((F - G) % MOD + MOD) % MOD);
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
正解
T1
上文说的差不多了。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MOD (ll)(1e9 + 7)
#define S(name, idx) ((name) & (1 << ((idx) - 1)))
template < typename T = int >
inline T read(void);
struct Edge{
Edge* nxt;
int to;
OPNEW;
}ed[2100000];
ROPNEW;
Edge* head[110000];
int N, K;
int Smx;
int opt[10][10];
struct Node{int S; int col;};
basic_string < Node > legal[40];
ll dp[110000][40][6];
ll merg[40][6];
void Clear(void){
for(int i = 0; i <= Smx; ++i)legal[i].clear();
for(int i = 0; i <= N; ++i)head[i] = npt;
for(int i = 0; i <= N; ++i)for(int S = 0; S <= Smx; ++S)for(int k = 1; k <= K; ++k)dp[i][S][k] = 0;
}
void TreeDP(int p = 1, int fa = 0){
for(auto i = head[p]; i; i = i->nxt)if(SON != fa)TreeDP(SON, p);
if(p != 1 && !head[p]->nxt){for(int i = 0; i < K; ++i)dp[p][1 << i][i + 1] = 1; return;}
memset(merg, 0, sizeof merg);
bool isbeg(true);
for(auto i = head[p]; i; i = i->nxt){
if(SON == fa)continue;
if(isbeg){
isbeg = false;
for(int S = 1; S <= Smx; ++S)for(int j = 1; j <= K; ++j)for(int k = 1; k <= K; ++k)(merg[S][j] += dp[SON][S][k]) %= MOD;
// printf("p is %d, after merge, merge is : \n", p);
// for(int S = 1; S <= Smx; ++S)for(int i = 1; i <= K; ++i)
// cout << "merg[" << i << "][" << bitset < 5 >(S) << "] = " << merg[S][i] << endl;
continue;
}
ll lst[40][6];
for(int S = 0; S <= Smx; ++S)for(int j = 1; j <= K; ++j)lst[S][j] = merg[S][j], merg[S][j] = 0;
ll sum[40]; memset(sum, 0, sizeof sum);
for(int S = 1; S <= Smx; ++S)for(int j = 1; j <= K; ++j)(sum[S] += dp[SON][S][j]) %= MOD;
for(int S1 = 1; S1 <= Smx; ++S1)
for(auto S2 : legal[S1])
(merg[S1 | S2.S][S2.col] += lst[S1][S2.col] * sum[S2.S] % MOD) %= MOD;
// printf("p is %d, after merge, merge is : \n", p);
// for(int S = 1; S <= Smx; ++S)for(int i = 1; i <= K; ++i)
// cout << "merg[" << i << "][" << bitset < 5 >(S) << "] = " << merg[S][i] << endl;
}
for(int S = 1; S <= Smx; ++S)
for(int i = 1; i <= K; ++i)
(dp[p][S | (1 << (i - 1))][i] += merg[S][i]) %= MOD;
// printf("p = %d\n", p);
// for(int S = 1; S <= Smx; ++S)
// for(int i = 1; i <= K; ++i){
// printf("dp[%d][", i); cout << bitset < 5 >(S); printf("] = %lld\n", dp[p][S][i]);
// }
}
int main(){
// freopen("color.in", "r", stdin);
// freopen("color.out", "w", stdout);
int T = read();
while(T--){
Clear();
N = read(), K = read();
Smx = (1 << K) - 1;
for(int i = 1; i <= K; ++i)for(int j = 1; j <= K; ++j)opt[i][j] = read();
for(int i = 2; i <= N; ++i){
int s = i, t = read();
head[s] = new Edge{head[s], t};
head[t] = new Edge{head[t], s};
}
for(int S1 = Smx; S1; S1 = (S1 - 1) & Smx)
for(int S2 = Smx; S2; S2 = (S2 - 1) & Smx){
int cur(-1);
bool flag(true);
for(int i = 1; i <= K; ++i){
if(!flag)break;
for(int j = 1; j <= K; ++j){
if(!flag)break;
if(S(S1, i) && S(S2, j)){
if(opt[i][j] != opt[j][i]){flag = false; break;}
if(!~cur)cur = opt[i][j];
else if(opt[i][j] != cur)flag = false;
}
}
}if(flag)legal[S1] += Node{S2, cur};
}
// for(int S = 1; S <= Smx; ++S)for(auto S2 : legal[S]){
// cout << bitset < 5 >(S) << "with" << bitset < 5 >(S2.S) << " col is" << S2.col << endl;
// }
TreeDP();
// for(int i = 1; i <= N; ++i)for(int S = 1; S <= Smx; ++S)for(int j = 1; j <= K; ++j)
// cout << "dp[" << i << "][" << j << "][" << bitset < 5 >(S) << "] = " << dp[i][S][j] << endl;
ll ans(0);
for(int S = 1; S <= Smx; ++S)for(int i = 1; i <= K; ++i)(ans += dp[1][S][i]) %= MOD;
printf("%lld\n", ans);
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
/*
2
5 2
1 2
2 1
1 2 1 4
5 2
1 2
1 1
1 2 1 4
*/
T2
提供一种复杂度正确但常数巨大码量较大的并不优秀的无脑做法，思路来自于模拟赛赛时口糊的，在 Luogu 上可以通过，但赛时在 LemonLime 测的时候大概是因为常数原因被卡的就剩 $ 20\texttt{pts} $。
首先我们不难想到 $ w_x \bmod{w_y} $ 即为链上次小值。这个不难证明，若我们选择最大值，那么其对较小值取模后一定小于较小值，而若我们选择次大值对最大值取模那么可以直接保留次小值。
然后呢最开始我看这道题没太仔细，以为 $ B $ 也是在链上找，于是考虑的是维护次次小和次次次小保留次次次小，当然这个是大错特错的，不仅没有考虑 $ B $ 是树上的，还没有考虑 $ A $ 不能重复权值但 $ B $ 可以。
于是在我发现问题后就尝试优化这个思路，最终的过程大概是这样的：
首先树剖显然，然后线段树上维护区间的不可重复的前 $ 5 $ 大值，以及最多重复一次（即有两个）的前 $ 5 $ 大值。然后对于合并子区间，我们考虑直接维护结构体然后重载 +，实现上用一个 basic_string 存子节点所有值然后排序并各种特判细节做一下即可，不难发现超大的常数就是卡在这里了，这东西某种意义上来讲可以认为其为 $ O(1) $ 的，但是实际上个人感觉平均大概有个 $ 10 $ 左右的常数。
然后修改较为简单不再赘述，对于查询直接按照树剖查询并合并，对于不能重复的前 $ 5 $ 大取其第二大作为 $ A $ 的答案，不存在则输出 -1。然后我们要再次查询整棵树的结果，在可重复两次的前 $ 5 $ 大中删去 $ A $ 的两个答案，此时不难理解为什么维护的是可以重复两次的。然后此时还需要分类讨论，如果结果不够说明只能找到两个相同的数，这样结果为 $ 0 $，如果最终剩下三个数且前两个为 $ 0 $，那么说明原来的为 $ a \gt b \gt c = d \gt e $，然后 $ a, b $ 被删除，此时如果我们不维护 $ e $ 答案将变为 $ 0 $，这也就是为什么我们要维护前 $ 5 $ 大而不是 $ 4 $，显然此时答案应为 $ e $。同时因为题里没有说 $ B $ 取不了的情况，且不难想到只要 $ n \ge 4 $ 那么 $ B $ 一定可以拿，所以姑且可以认为题目保证了 $ n \ge 4 $。
当然这里也浅提一下，如果用 multiset 维护 $ B $ 的话就只需要维护最大和次大就可以了，常数小且好写，也不知道我模拟赛的时候为什么没想到，估计是开始读错题之后先入为主了。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template < typename T = int >
inline T read(void);
struct Edge{
Edge* nxt;
int to;
OPNEW;
}ed[210000];
ROPNEW;
Edge* head[110000];
int N, Q;
ll w[110000];
int dep[110000], dfn[110000], hson[110000], siz[110000], ffa[110000], tp[110000], idx[110000];
void dfs_pre(int p = 1, int fa = 0){
dep[p] = dep[fa] + 1;
siz[p] = 1;
ffa[p] = fa;
for(auto i = head[p]; i; i = i->nxt){
if(SON == fa)continue;
dfs_pre(SON, p);
siz[p] += siz[SON];
if(siz[hson[p]] < siz[SON])hson[p] = SON;
}
}
void dfs_make(int p = 1, int top = 1){
tp[p] = top;
static int cdfn(0);
dfn[p] = ++cdfn;
idx[cdfn] = p;
if(hson[p])dfs_make(hson[p], top);
for(auto i = head[p]; i; i = i->nxt)
if(SON != ffa[p] && SON != hson[p])
dfs_make(SON, SON);
}
struct Node{
ll v[6], vu[6]; //v_max_with_2, v_unique
Node(void){memset(v, 0, sizeof v), memset(vu, 0, sizeof vu);}
friend Node operator + (const Node &a, const Node &b){
Node ret;
basic_string < ll > values;
for(int i = 1; i <= 5; ++i){
if(a.v[i])values += a.v[i];
if(b.v[i])values += b.v[i];
}sort(values.begin(), values.end(), greater < ll >());
for(auto it = values.begin(); it != values.end() && next(it) != values.end() && next(it, 2) != values.end();)
if(*it == *next(it) && *next(it) == *next(it, 2))it = values.erase(it);
else advance(it, 1);
for(int i = 1; i <= 5; ++i)
ret.v[i] = (int)values.size() >= i ? values.at(i - 1) : 0;
values.clear();
for(int i = 1; i <= 5; ++i){
if(a.vu[i])values += a.vu[i];
if(b.vu[i])values += b.vu[i];
}sort(values.begin(), values.end(), greater < ll >());
values.erase(unique(values.begin(), values.end()), values.end());
for(int i = 1; i <= 5; ++i)
ret.vu[i] = (int)values.size() >= i ? values.at(i - 1) : 0;
return ret;
}
};
class SegTree{
private:
Node mx[110000 << 2];
#define LS (p << 1)
#define RS (LS | 1)
#define MID ((gl + gr) >> 1)
public:
void Pushup(int p){
mx[p] = mx[LS] + mx[RS];
}
void Build(int p = 1, int gl = 1, int gr = N){
if(gl == gr)return mx[p].v[1] = mx[p].vu[1] = w[idx[gl = gr]], void();
Build(LS, gl, MID), Build(RS, MID + 1, gr);
Pushup(p);
}
void Modify(int id, int v, int p = 1, int gl = 1, int gr = N){
if(gl == gr)return mx[p].v[1] += v, mx[p].vu[1] += v, void();
if(id <= MID)Modify(id, v, LS, gl, MID);
else Modify(id, v, RS, MID + 1, gr);
Pushup(p);
}
Node Query(int l, int r, int p = 1, int gl = 1, int gr = N){
// printf("Querying l = %d, r = %d\n", l, r);
if(l <= gl && gr <= r)return mx[p];
if(gr < l || r < gl)return Node();
return Query(l, r, LS, gl, MID) + Query(l, r, RS, MID + 1, gr);
}
}st;
void Make(int s, int t){
Node cur;
while(tp[s] != tp[t]){
if(dep[tp[s]] < dep[tp[t]])swap(s, t);
cur = cur + st.Query(dfn[tp[s]], dfn[s]);
s = ffa[tp[s]];
}if(dep[s] < dep[t])swap(s, t);
cur = cur + st.Query(dfn[t], dfn[s]);
if(!cur.vu[1] || !cur.vu[2]){printf("-1\n"); return;}
Node ret = st.Query(1, N);
basic_string < ll > tmp;
for(int i = 1; i <= 5; ++i)if(ret.v[i])tmp += ret.v[i];
for(int i = 1; i <= 2; ++i)
if(find(tmp.begin(), tmp.end(), cur.vu[i]) != tmp.end())
tmp.erase(find(tmp.begin(), tmp.end(), cur.vu[i]));
if((int)tmp.size() < 2 || ((int)tmp.size() == 2 && tmp.at(0) == tmp.at(1))){printf("%lld 0\n", cur.vu[2]); return;}
if(tmp.size() == 3 && tmp.at(0) == tmp.at(1)){printf("%lld %lld\n", cur.vu[2], tmp.at(2)); return;}
printf("%lld %lld\n", cur.vu[2], tmp.at(0) == tmp.at(1) ? tmp.at(2) : tmp.at(1));
// for(int i = 1; i <= 5; ++i)printf("mxchain mxvu[%d] = %lld\n", i, cur.vu[i]);
// for(int i = 1; i <= 5; ++i)printf("mxtree mxv[%d] = %lld\n", i, ret.v[i]);
}
int main(){
// freopen("game.in", "r", stdin);
// freopen("game.out", "w", stdout);
N = read();
for(int i = 1; i <= N - 1; ++i){
int s = read(), t = read();
head[s] = new Edge{head[s], t};
head[t] = new Edge{head[t], s};
}dfs_pre(), dfs_make();
for(int i = 1; i <= N; ++i)w[i] = read();
st.Build();
Q = read();
while(Q--){
int opt = read(), x = read(), y = read();
if(opt == 0)st.Modify(dfn[x], y);
else Make(x, y);
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
/*
7
1 2
2 3
2 5
1 5
5 6
5 7
5 5 3 2 1 5 3
6
1 3 5
1 2 5
1 2 1
0 2 1
1 2 5
1 2 1
*/
T3
显然合法区间的一个合法子序列一定可以转换为递增或递减的，于是令 $ dp(i) $ 表示 $ i $ 之后不包括 $ i $ 的能转移到的点的个数，有 $ dp(n) = 0 $，有转移 $ dp(i) = dp(j) + cnt(j, n, a_i + 1, a_j) \(。\) j $ 表示满足 $ a_i \lt a_j \le a_i + k, j \gt i $ 的第一个 $ j \(，\) cnt(l, r, d, u) $ 表示在 $ a_i \in [d, u] $ 的 $ i \in [l, r] $ 的数量。式子的意义即 $ dp(j) $ 代表了所有 $ \gt a_j $ 的，我们只需要在此基础上再加上区间内所有 $ [a_i + 1, a_j] $ 的即可不重不漏。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MXV (100010)
template < typename T = int >
inline T read(void);
int N, K;
ll ans(0);
ll A[510000];
unordered_map < int, ll > cnt;
ll dp[510000];
class SegTree{
private:
ll tr[110000 << 2];
int mn[110000 << 2];
#define LS (p << 1)
#define RS (LS | 1)
#define MID ((gl + gr) >> 1)
public:
SegTree(void){memset(mn, 0x3f, sizeof mn);}
void Pushup(int p){
tr[p] = tr[LS] + tr[RS];
mn[p] = min(mn[LS], mn[RS]);
}
void Modify(int val, int id, int p = 1, int gl = 1, int gr = MXV){
// undel.insert(p);
if(gl == gr)return tr[p]++, mn[p] = min(mn[p], id), void();
if(val <= MID)Modify(val, id, LS, gl, MID);
else Modify(val, id, RS, MID + 1, gr);
Pushup(p);
}
void Assign(int val, int p = 1, int gl = 1, int gr = MXV){
tr[p] = 0, mn[p] = 0x3f3f3f3f;
if(gl == gr)return;
if(val <= MID)Assign(val, LS, gl, MID);
else Assign(val, RS, MID + 1, gr);
}
int QueryMin(int l, int r, int p = 1, int gl = 1, int gr = MXV){
if(l <= gl && gr <= r)return mn[p];
if(r < gl || gr < l)return 0x3f3f3f3f;
return min(QueryMin(l, r, LS, gl, MID), QueryMin(l, r, RS, MID + 1, gr));
}
ll QueryCnt(int l, int r, int p = 1, int gl = 1, int gr = MXV){
if(l <= gl && gr <= r)return tr[p];
if(r < gl || gr < l)return 0;
return QueryCnt(l, r, LS, gl, MID) + QueryCnt(l, r, RS, MID + 1, gr);
}
}st;
ll Make(void){
for(int i = 0; i <= N; ++i)dp[i] = 0;
ll ret(0);
for(int i = N; i >= 1; --i){
int p = st.QueryMin(A[i] + 1, A[i] + K);
dp[i] = p == 0x3f3f3f3f ? 0 : dp[p] + st.QueryCnt(A[i] + 1, A[p]);
st.Modify(A[i], i);
ret += dp[i];
}
for(int i = 1; i <= N; ++i)st.Assign(A[i]);
return ret;
}
int main(){
int T = read();
while(T--){
ans = 0;
N = read(), K = read();
for(int i = 1; i <= N; ++i)cnt[A[i] = read()]++;
for(auto v : cnt)ans += ((v.second) * (v.second + 1)) >> 1;
cnt.clear();
ans += Make(), reverse(A + 1, A + N + 1), ans += Make();
printf("%lld\n", ans);
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
T4
考虑发现，若两区间存在包含关系，即 $ X $ 包含 $ Y $，那么若 $ X $ 存在，则 $ Y $ 的存在与不存在会分别对奇数和偶数贡献 $ 1 $，则 $ X $ 存在的方案总贡献为 $ 0 $，那么我们可以直接认为 $ X $ 不存在。同时发现若存在 $ l_1 \lt l_2 \lt l_3 \lt r_1 $，那么是可以直接删除 $ [l_3, r_3] $ 的，同上理解。然后最终就剩余多个区间且每个区间最多左右各与一个区间有交。于是考虑对于一次询问找到询问 $ l $ 的相邻的两个区间，然后向后跳，每次跳到与其完全无交的最近区间。不难发现跳的过程可以倍增维护，注意处理好亿点细节即可。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define rng(x) (rng.at((x) - 1))
#define INF (0x3f3f3f3f)
template < typename T = int >
inline T read(void);
int N, Q;
int dp[210000][25];
struct Range{
int l, r;
friend const bool operator < (const Range &a, const Range &b){
return a.l == b.l ? a.r > b.r : a.l < b.l;
}
}rngt[210000];
basic_string < Range > rng;
int main(){
N = read(), Q = read();
for(int i = 1; i <= N; ++i)rngt[i].l = read(), rngt[i].r = read();
sort(rngt + 1, rngt + N + 1);
int curR(INF);
for(int i = N; i >= 1; --i){
if(rngt[i].r >= curR)continue;
curR = rngt[i].r;
rng += rngt[i];
}sort(rng.begin(), rng.end());
int tot = rng.size();
int nxt(1);
for(int cur = 1; cur <= tot; ++cur){
while(nxt <= tot && rng(nxt).l <= rng(cur).r)++nxt;
dp[cur][0] = nxt;
}for(int i = 0; i <= 20; ++i)dp[tot + 1][i] = tot + 1;
for(int j = 1; j <= 20; ++j)
for(int i = 1; i <= tot; ++i)
dp[i][j] = dp[dp[i][j - 1]][j - 1];
while(Q--){
int l = read(), r = read();
auto it = lower_bound(rng.begin(), rng.end(), Range{l, INF});
if(it == rng.end() || it->l != l){printf("0\n"); continue;}
if(it->r == r){printf("998244352\n"); continue;}
auto nxt = lower_bound(rng.begin(), rng.end(), Range{l + 1, INF});
if(nxt == rng.end() || nxt->l > it->r || nxt->r > r){printf("0\n"); continue;}
int cur = distance(rng.begin(), it) + 1;
int cnxt = distance(rng.begin(), nxt) + 1;
bool ret(0);
for(int j = 20; j >= 0; --j)
if(dp[cur][j] <= tot && rng(dp[cur][j]).r <= r)
cur = dp[cur][j], ret ^= j ? 0 : 1;
for(int j = 20; j >= 0; --j)
if(dp[cnxt][j] <= tot && rng(dp[cnxt][j]).r <= r)
cnxt = dp[cnxt][j], ret ^= j ? 0 : 1;
if(cur == cnxt || (rng(cur).r != r && rng(cnxt).r != r)){printf("0\n"); continue;}
printf("%d\n", ret ? 998244352 : 1);
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
UPD
update-2023_01_17 初稿
标签：return,17,int,2023.01,void,ret,SON,小结,define From： https://www.cnblogs.com/tsawke/p/17124343.html