2022 年杭电多校第二场补题记录

A A Static Query on Tree

题意：给定一个 $1$ 为根的内向树，$q$ 次询问，每次给出三个点集合 $A,B,C$，问有几个点能从 $A$ 集合和 $B$ 集合中至少一个点到达，并且到达 $C$ 中的一个点。 保证 $\sum |A|+\sum |B|+\sum |C|\le 2\times 10^5$。

解法：看到多次询问点集并且点集大小和有限制的，通常可以考虑建立虚树。对于每次询问建立虚树，并根据集合打上不同的标记，然后进行 dfs，对于一个节点，判定其合法的标准为：子树中存在 $A$ 集合标记的节点和 $B$ 集合标记的节点，且递归栈中存在 $C$ 节点标记节点，那么从它开始到它的虚树上的父亲，对应的原树上的一条链就均要计入答案。对于 $1$ 节点的合法性判断可以特判处理。

此处借用队友代码。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define max(x,y) (x>y?x:y)
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
using namespace std;
const int N=2e5+3;
struct hh{int to,nxt;
}e[N<<1];
int n,m,fir[N],num,fa[N][20],dep[N],cnt,dfn[N],siz[N],sta[N],tp,bo[N][3],f[N][3];
int di[N],ans;
vector<int>E[N];
IL LL in(){char c;int f=1;while((c=getchar())<'0'||c>'9')if(c=='-') f=-1;LL x=c-'0';while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';return x*f;
}bool cmp1(int x,int y){return dfn[x]<dfn[y];}IL void add(int x,int y){e[++num]=(hh){y,fir[x]},fir[x]=num;
}IL void clear(){num=cnt=0,memset(fir,0,sizeof(fir));memset(fa,0,sizeof(fa));
}IL void Add(int x,int y){E[x].push_back(y);
}void dfs1(int u,int f){fa[u][0]=f,siz[u]=1,dfn[u]=++cnt,dep[u]=dep[f]+1;for(int i=0;fa[u][i];++i)fa[u][i+1]=fa[fa[u][i]][i];for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)dfs1(v,u),siz[u]+=siz[v];
}IL int Lca(int x,int y){if(dep[x]<dep[y]) swap(x,y);for(int i=17;~i;--i)if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];if(x==y) return x;for(int i=17;~i;--i)if(fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i];return fa[x][0];
}IL void ins(int x){if(!tp){sta[++tp]=x;return;}int lca=Lca(sta[tp],x);if(lca==sta[tp]){sta[++tp]=x;return;}while(dep[lca]<dep[sta[tp-1]]) Add(sta[tp-1],sta[tp]),--tp;Add(lca,sta[tp]),--tp;if(lca!=sta[tp]) sta[++tp]=lca;sta[++tp]=x;
}void dfs2(int u,int fa){f[u][2]=f[fa][2]|bo[u][2];for(int i=0;i<E[u].size();++i){int v=E[u][i];dfs2(v,u);f[u][0]|=f[v][0],f[u][1]|=f[v][1];if(f[u][2]&&(f[v][0]&&f[v][1])) ans+=dep[v]-dep[u]-1;}f[u][0]|=bo[u][0],f[u][1]|=bo[u][1];if(f[u][2]&&(f[u][0]&&f[u][1])) ++ans;
}void dele(int u,int fa){f[u][0]=f[u][1]=f[u][2]=bo[u][0]=bo[u][1]=bo[u][2]=0;for(int i=0;i<E[u].size();++i) dele(E[u][i],u);E[u].clear();
}
void solve(){n=in(),m=in(),clear();for(int i=2;i<=n;++i) add(in(),i);dfs1(1,0);int nn[3];while(m--){di[0]=ans=0;for(int i=0;i<=2;++i) nn[i]=in();for(int i=0;i<=2;++i)for(int j=1;j<=nn[i];++j)bo[di[++di[0]]=in()][i]=1;sort(di+1,di+di[0]+1),di[0]=unique(di+1,di+di[0]+1)-di-1;sort(di+1,di+di[0]+1,cmp1);for(int i=1;i<=di[0];++i) ins(di[i]);while(tp>1) Add(sta[tp-1],sta[tp]),--tp;dfs2(sta[1],0),dele(sta[1],0);tp=0;printf("%d\n",ans);}
}
int main()
{int T=in();while(T--) solve();return 0;
}

B C++ to Python

题意：将 C++ 中 std::make_tuple换成 python 中的括号数组。

解法：删去 std::make_tuple即可。

C Copy

题意：给定一个长度为 $n$ 的序列 { a n } \{a_n\} {an​}，$q$ 次操作：

1. 给定区间 $[l,r]$，复制该连续子序列并将其复制到 $r+1$ 处，即原序列由 $a_{l-1},a_l,a_{l+1},\cdots ,a_r,a_{r+1},\cdots$ 变成 $a_{l-1},a_l,a_{l+1},\cdots ,a_r,a_l,a_{l+1},\cdots ,a_r,a_{r+1},\cdots$。
2. 查询 $a_x$。保证 $x\le n$。

最后输出所有查询操作的异或值。$n,q\le 2\times 10^5$。

解法：由于最后是输出异或值，因而如果同一个值被询问偶数次就等同于没有询问，所以原序列每个值对答案的贡献只有 $0$ 次或 $1$ 次，可以使用 bitset数组 $f$ 来存储每个值是否会对答案造成贡献。

对于一次复制操作 $[l,r]$，其影响为：对于后面所有的询问 $x$，若 $x\ge r$，则 $x\leftarrow x-(r-l+1)$。因而倒序去进行操作：对于一次查询操作 $x$，将 $f_x\leftarrow f_x\oplus 1$，表示原序列第 $x$ 个数会被异或一次；对于平移操作，即是将 $f$ 的上侧部分（$[r+1,n]$）向低侧平移 $r-l+1$ 个单位，即右移，表示原先在 $x$ 的数字因为复制操作被移动到了 $x+(r-l+1)$ 处；对于下侧部分（$[1,r]$），则保持不变，再将二者取异或即可。

注意：bitset低位位于高位的右侧，因而从高位到低位是右移，和正常 bit 存储方式相同，但和数组存储方式不同。

#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
struct operation
{int op;int l, r, x;operation(int _op, int _x){op = _op;x = _x;}operation(int _op, int _l, int _r){op = _op;l = _l;r = _r;}
};
int main()
{int t, n, q;scanf("%d", &t);while(t--){int op, l, r;bitset<N> mask;scanf("%d%d", &n, &q);vector<int> a(n + 1);for (int i = 1; i <= n;i++)scanf("%d", &a[i]);vector<operation> que;for (int i = 0; i < q;i++){scanf("%d", &op);if (op == 1){scanf("%d%d", &l, &r);que.emplace_back(1, l, r);}else{scanf("%d", &l);que.emplace_back(2, l);}}bitset<N> f(0), high, low;for (int i = q - 1; i >= 0;i--){if (que[i].op == 1){int l = que[i].l, r = que[i].r;low = f & (~bitset<N>(0) >> (N - r - 1));high = f & (~bitset<N>(0) << (r + 1));f = low ^ (high >> (r + 1 - l));}elsef[que[i].x].flip();}int ans = 0;for (int i = 1; i <= n; i++)if (f[i])ans ^= a[i];printf("%d\n", ans);}return 0;
}

D Keychains

题意：给定空间两个圆，求是否相扣。$T$ 组测试数据，$T\le 1\times 10^5$。

解法：找到两圆所在平面的交线 $l$，记两圆圆心为 $O_1,O_2$，做 $O_1$ 到 $l$ 的垂线，记垂足为 $H$，此时可以根据垂径定理得到直线 $l$ 与第一个圆 $\odot O_1$的交点 $P_1,P_2$，最后判定 $P_1$ 与 $P_2$ 是否一个在 $\odot O_2$ 外一个在内即可。

如何快速找到垂足 $H$：$l$ 的方向向量由两平面的法向量 $\vec{a},\vec{b}$ 的叉积 $\vec{a}\times \vec{b}$ 给出。此时考虑直线 $l$ 上点 $H$， 有 $H$ 在两平面上，同时 $O_{1}H\perp l$，因而构造了三个方程，可以使用克拉默法则进行求解。

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-6;
vector<double> operator *(vector<double> a, vector<double> b)
{return {a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2], a[0] * b[1] - a[1] * b[0]};
}
vector<double> operator -(vector<double> a, vector<double> b)
{return {a[0] - b[0], a[1] - b[1], a[2] - b[2]};
}
vector<double> operator +(vector<double> a, vector<double> b)
{return {a[0] + b[0], a[1] + b[1], a[2] + b[2]};
}
vector<double> operator *(double k, vector<double> b)
{return {k * b[0], k * b[1], k * b[2]};
}
double operator ^(vector<double> a, vector<double> b)
{double ans = 0;for (int i = 0; i <= 2;i++)ans += a[i] * b[i];return ans;
}
double det(vector<double> a, vector<double> b, vector<double> c)
{auto d = b * c;return a ^ d;
}
double dis(vector<double> a, vector<double> b)
{double ans = 0;for (int i = 0; i <= 2;i++)ans += (a[i] - b[i]) * (a[i] - b[i]);return sqrt(ans);
}
double len(vector<double> a)
{double ans = 0;for (int i = 0; i <= 2;i++)ans += a[i] * a[i];return sqrt(ans);
}
bool check_para(vector<double> a, vector<double> b)
{auto ans = a * b;for (int i = 0; i <= 2;i++)if (fabs(ans[i]) > eps)return false;return true;
}
int main()
{int t;scanf("%d", &t);while(t--){vector<double> a(3), b(3), dira(3), dirb(3);double ra, rb;for (int i = 0; i <= 2;i++)scanf("%lf", &a[i]);for (int i = 0; i <= 2;i++)scanf("%lf", &dira[i]);scanf("%lf", &ra);for (int i = 0; i <= 2;i++)scanf("%lf", &b[i]);for (int i = 0; i <= 2;i++)scanf("%lf", &dirb[i]);scanf("%lf", &rb);if(check_para(dira, dirb))printf("No\n");else{auto dir = dira * dirb;vector<double> row1 = {dira[0], dirb[0], dir[0]};vector<double> row2 = {dira[1], dirb[1], dir[1]};vector<double> row3 = {dira[2], dirb[2], dir[2]};vector<double> row4 = {dira ^ a, dirb ^ b, dir ^ a};double d = det(row1, row2, row3);vector<double> foot = {det(row4, row2, row3) / d, det(row1, row4, row3) / d, det(row1, row2, row4) / d};double verdis = dis(foot, a);double nowlen = sqrt(ra * ra - verdis * verdis);auto in1 = foot + nowlen / len(dir) * dir, in2 = foot - nowlen / len(dir) * dir;if ((dis(in1, b) <= rb) ^ (dis(in2, b) <= rb))printf("Yes\n");elseprintf("No\n");}}return 0;
}

E Slayers Come

题意：给定 $n$ 个怪物，每个怪物有血量 $a_i$ 与攻击值 $b_i$。对于一次攻击 $(x_i,L_i,R_i)$，表示第一个攻击 $x_i$ 怪物，并且从 $x_i$ 开始向左，若 $a_j-L_i\ge b_{j+1}$，则 $j$ 怪物也会被打死；从 $x_i$ 向右，若 $a_j-R_i\ge b_{j+1}$ 则怪物 $j$ 也会被打死。给定 $m$ 次攻击，问有多少种攻击组合可以打死一次全部的怪物。每次攻击完所有怪物都会恢复。$n,m\le 2\times 10^5$。

解法：先根据 $a_j-b_{j+1}$ 从大到小排序，$L_i$ 从大到小排序，然后并查集维护每个点向左最远可以到多少；对于 $R_i$ 同理。这样就可以整理出 $m$ 个区间 $[l_i,r_i]$，之后就是一个区间覆盖问题：给定 $m$ 个区间，有多少种方法可以覆盖完整整个区间。

考虑以下的 dp：$f_i$ 表示覆盖完 $[1,i]$，且后面可以覆盖或者不覆盖的方案。对所有区间按右端点从小到大排序，则对于区间 $[l,r]$，$f_r=\sum _{j=l-1}^r{f}_j$——可以从之前最远覆盖到 $j,j\in [l-1,r]$，然后延申覆盖。同时，对于这个区间没办法直接连接的区间，即右端点范围在 $[0,l-2]$ 区间，当前区间的加入对这一部分没有任何影响，因而它的加入和不加入都是可以的，所以这一部分 $f_i\leftarrow 2f_i$。因而使用线段树维护区间和即可。

#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
class segment_tree
{struct node{long long sum;long long tag;node(){sum = 0;tag = 1;}};int n;vector<node> t;void pushdown(int place, int left, int right){if (t[place].tag > 1){int mid = (left + right) >> 1;update(place << 1, left, mid, left, mid, t[place].tag);update(place << 1 | 1, mid + 1, right, mid + 1, right, t[place].tag);t[place].tag = 1;}}void update(int place, int left, int right, int start, int end, long long x){if (start <= left && right <= end){t[place].sum = t[place].sum * x % mod;t[place].tag = t[place].tag * x % mod;return;}pushdown(place, left, right);int mid = (left + right) >> 1;if (start <= mid)update(place << 1, left, mid, start, end, x);if (end > mid)update(place << 1 | 1, mid + 1, right, start, end, x);t[place].sum = (t[place << 1].sum + t[place << 1 | 1].sum) % mod;}void update(int place, int left, int right, int start, long long x){if (left == right){t[place].sum = (t[place].sum + x) % mod;return;}pushdown(place, left, right);int mid = (left + right) >> 1;if (start <= mid)update(place << 1, left, mid, start, x);elseupdate(place << 1 | 1, mid + 1, right, start, x);t[place].sum = (t[place << 1].sum + t[place << 1 | 1].sum) % mod;}long long query(int place, int left, int right, int start, int end){if (start <= left && right <= end)return t[place].sum;pushdown(place, left, right);int mid = (left + right) >> 1;long long ans = 0;if (start <= mid)ans = (ans + query(place << 1, left, mid, start, end)) % mod;if (end > mid)ans = (ans + query(place << 1 | 1, mid + 1, right, start, end)) % mod;return ans;}public:segment_tree(int n){this->n = n;t.resize(4 * n + 5);}void mul(int l, int r, long long x){if (l > r)return;update(1, 0, n, l, r, x);}void add(int l, long long x){update(1, 0, n, l, x);}long long query(int l, int r){if (l > r)return 0ll;return query(1, 0, n, l, r);}
};
struct node
{int x, l, r;int id;node(int _x, int _l, int _r, int _id){x = _x;l = _l;r = _r;id = _id;}
};
class DSU
{vector<int> father;int n;public:DSU(int n){father.resize(n + 1);for (int i = 1; i <= n;i++)father[i] = i;this->n = n;}int getfather(int x){return father[x] == x ? x : father[x] = getfather(father[x]);}void merge(int u, int v){u = getfather(u);v = getfather(v);if (u == v)return;father[u] = v;}
};int main()
{int t, n, m;scanf("%d", &t);while(t--){scanf("%d%d", &n, &m);vector<int> a(n + 1), b(n + 1);for (int i = 1; i <= n;i++)scanf("%d%d", &a[i], &b[i]);vector<node> skill;vector<pair<int, int>> to_left, to_right;for (int i = 0, x, l, r; i < m;i++){scanf("%d%d%d", &x, &l, &r);skill.emplace_back(x, l, r, i);}auto cmp1 = [&](node a, node b){return a.l > b.l;};for (int i = 2; i <= n;i++)to_left.emplace_back(a[i] - b[i - 1], i);for (int i = 1; i < n;i++)to_right.emplace_back(a[i] - b[i + 1], i);sort(skill.begin(), skill.end(), cmp1);sort(to_left.begin(), to_left.end(), greater<pair<int, int>>());vector<int> lbound(m), rbound(m);DSU t1(n);for (int i = 0, j = 0; i < m;i++){while (j < to_left.size() && to_left[j].first >= skill[i].l){t1.merge(to_left[j].second, to_left[j].second - 1);j++;}lbound[skill[i].id] = t1.getfather(skill[i].x);}auto cmp2 = [&](node a, node b){return a.r > b.r;};sort(skill.begin(), skill.end(), cmp2);sort(to_right.begin(), to_right.end(), greater<pair<int, int>>());DSU t2(n);for (int i = 0, j = 0; i < m;i++){while (j < to_right.size() && to_right[j].first >= skill[i].r){t2.merge(to_right[j].second, to_right[j].second + 1);j++;}rbound[skill[i].id] = t2.getfather(skill[i].x);}vector<vector<int>> interval(n + 1);for (int i = 0; i < m;i++)interval[rbound[i]].push_back(lbound[i]);segment_tree t(n);t.add(0, 1);for (int i = 1; i <= n;i++)for (auto j : interval[i]){t.add(i, t.query(j - 1, i));t.mul(0, j - 2, 2);}printf("%lld\n", t.query(n, n));}return 0;
}

H Keyboard Warrior

题意：给定一个操作序列 $(c,k)$，若 $c$ 为小写字符则往缓冲区添加 $k$ 个 $c$ 字符；若为 -则删除最后的 $k$ 个字符。问是否存在一个时刻，给定的一个串 $S$ 为缓冲区中字符串的一个连续子串。$|S|\le 2\times 10^5$，$0\le k\le 1\times 10^9$。

解法：首先将字符串头尾两部分相同的字符全部压缩起来表示成该字符出现多少次，同时将操作序列也进行压缩。考虑使用栈维护当前的缓冲区，栈中存储 $(c,k)$。由于该题中会不断的添加和删除字符，因而考虑使用哈希——哈希可以方便的维护增加或者删除字符。与栈相对应的记录当前栈的缓冲区长度和当前状态下对应的哈希值。

此题中哈希值的特殊性在于其一次性加入大量的相同字符。对于一个普通哈希 $\sum c_i{p}^i$，一次性加入 $k$ 个字符 $c$ 的哈希值为 $\frac{p^k-1}{p-1}$，可以 $\mathcal{O}(1)$ 的计算。考虑什么时候出现子串——（1）栈顶插入字符是 $S$ 的最后一个字符，且其出现次数大于等于 $S$ 末尾连续相同长度；（2）连续的中间部分，这部分必须和栈中完全一样；（3）开头字符也是和栈中对应位置插入字符相同，且长度大于等于开头连续相同长度。因而当第一个条件满足时，如果栈中也进行压缩存储：如存在相邻的 $(c,k_1),(c,k_2)$ 压缩合并成 $(c,k_1+k_2)$，则中间部分必然和栈中对应部分长度完全相同且不会分裂块，此时在栈中二分，需要让栈中若干个操作字符总长恰好和 $S$ 掐头去尾长度完全相同，且哈希值相同；最后检查头部是否满足字符相同且长度更长。因而时间复杂度 $\mathcal{O}(n\log n)$。具体细节参看代码。

#include <bits/stdc++.h>
using namespace std;
const int N = 2000000;
char a[N + 5], buf[10];
vector<pair<char, long long>> trans(vector<pair<char, long long>> que)
{vector<pair<char, long long>> ans;int n = que.size();for (int i = 0; i < n;){int j = i;long long times = 0;while (j < n && que[i].first == que[j].first){times += que[j].second;j++;}if (times)ans.emplace_back(que[i].first, times);i = j;}return ans;
}
const long long base = 37, mod = 998244353;
long long power(long long a, long long x)
{long long ans = 1;bool flag = 0;x %= (mod - 1);while(x){if (x & 1)ans = ans * a % mod;a = a * a % mod;x >>= 1;}return ans;
}
long long inv(long long a)
{return power(a, mod - 2);
}
long long cal(char ch, long long len)
{return (power(base, len) - 1 + mod) % mod * inv(base - 1) % mod * (ch - 97) % mod;
}
int main()
{int t, n, q;long long k;scanf("%d", &t);for (int o = 1; o <= t;o++){scanf("%d%d", &n, &q);scanf("%s", a + 1);vector<long long> ha(n + 1, 0);for (int i = 1, th = 1; i <= n; i++, th = 1ll * th * base % mod)ha[i] = (ha[i - 1] + 1ll * (a[i] - 97) * th % mod) % mod;vector<pair<char, long long>> op;for (int i = 0; i < q;i++){scanf("%s%lld", buf, &k);op.emplace_back(buf[0], k);}op = trans(op);int backlen = 0, frontlen = 0;for (int i = n; i >= 1;i--)if (a[i] == a[n])backlen++;elsebreak;for (int i = 1; i <= n;i++)if (a[i] == a[1])frontlen++;elsebreak;vector<long long> len, pre;auto cal_st_hash = [&](int x, int y){long long ans = pre[y];if(x)ans = (ans - pre[x - 1] + mod) % mod * inv(power(base, len[x - 1])) % mod;return ans;};auto cal_a_hash = [&](int x, int y){long long ans = ha[y];if(x)ans = (ans - ha[x - 1] + mod) % mod * inv(power(base, x - 1)) % mod;return ans;};vector<pair<char, long long>> st;bool ans = 0;int count = 0;for (auto i : op){count++;if (i.first == '-'){long long del = 0;while (!st.empty() && del + st.back().second <= i.second){len.pop_back();pre.pop_back();del += st.back().second;st.pop_back();}if(!st.empty() && del < i.second){long long dif = st.back().second - (i.second - del);auto temp = st.back();temp.second = dif;len.pop_back();pre.pop_back();st.pop_back();long long nowlen = dif;long long nowhash = cal(temp.first, dif) * power(base, len.empty() ? 0 : len.back()) % mod;len.push_back(len.empty() ? dif : len.back() + dif);pre.push_back(pre.empty() ? nowhash : (pre.back() + nowhash) % mod);st.push_back(temp);}continue;}if (!st.empty() && st.back().first == i.first){auto temp = st.back();st.pop_back();len.pop_back();pre.pop_back();temp.second += i.second;long long nowlen = temp.second;long long nowhash = cal(temp.first, nowlen) * power(base, len.empty() ? 0 : len.back()) % mod;len.push_back(len.empty() ? nowlen : len.back() + nowlen);pre.push_back(pre.empty() ? nowhash : (pre.back() + nowhash) % mod);st.push_back(temp);}else{st.push_back(i);long long nowhash = cal(i.first, i.second) * power(base, len.empty() ? 0 : len.back()) % mod;len.push_back(len.empty() ? i.second : len.back() + i.second);pre.push_back(pre.empty() ? nowhash : (pre.back() + nowhash) % mod);}if (backlen == n){if (!st.empty() && st.back().first == a[n] && st.back().second >= n){ans = 1;break;}}else if(backlen + frontlen == n){int siz = st.size();if (siz >= 2 && st[siz - 1].first == a[n] && st[siz - 1].second >= backlen && st[siz - 2].first == a[1] && st[siz - 2].second >= frontlen){ans = 1;break;}}else{int censt = frontlen + 1, cened = n - backlen;long long orihash = cal_a_hash(censt, cened), cenlen = cened - censt + 1;if (!st.empty() && st.back().first == a[n] && st.back().second >= backlen){int l = 0, r = st.size() - 2, pos = -1;while (l <= r){int mid = (l + r) >> 1;long long range_sum = len[st.size() - 2] - (mid ? len[mid - 1] : 0);if(range_sum == cenlen){pos = mid;break;}if(range_sum > cenlen)l = mid + 1;elser = mid - 1;}if (pos != -1){long long st_hash = cal_st_hash(pos, st.size() - 2);if (pos >= 1 && st[pos - 1].first == a[1] && st[pos - 1].second >= frontlen && st_hash == orihash){ans = 1;break;}}}}}if(ans)printf("yes\n");elseprintf("no\n");}return 0;
}

I ShuanQ

题意：给定一密码体制 $\mathcal{K}$：选定一秘密质数模数 $M$，公钥为 $P$，密钥为 $Q$，满足 $PQ\equiv 1(\mathrm{mod}M)$，加密过程为 $c=Px\mathrm{mod}M$，解密过程为 $x=Qc\mathrm{mod}M$。已知 $P,Q,c$，求 $x$ 或报告不存在。$P,Q\le 2\times 10^6$。

解法：$kM=PQ-1$，因而暴力枚举 $PQ-1$ 的质因子，满足大于 $P,Q$ 即可。这样的质因子至多一个。

K DOS Card

题意：给定序列 { x n } \{x_n\} {xn​}，$q$ 次询问，每次给定区间 $[l,r]$，问从中选出两对数字 $(a,b),(c,d),a<b,c<d$，且 $a,b,c,d$ 互不相同，$x_a^2-x_b^2+x_c^2-x_d^2$ 的最大值。$n,q\le 2\times 10^5$。

解法：区间合并线段树。记加的数字为 $i$，减的数字为 $j$，则合法的方案有 $iijj$，$ijij$。考虑维护以下几种可以区间合并的信息：

$i$：$\max (i_l,i_r)$；

$j$：$\max (j_l,j_r)$

$ij$：$\max (i_l+j_r,i{j}_l,i{j}_r)$

$ji$：$\max (j_l+i_r,j{i}_l,j{i}_r)$

$ii$：$\max (i_l+i_r,i{i}_l,i{i}_r)$

$jj$：$\max (j_l+j_r,j{j}_l,j{j}_r)$

$iij$：$\max (ii{j}_l,i_l+i{j}_r,i{i}_l+j_r,ii{j}_r)$

$ijj$：$\max (ij{j}_l,i{i}_l+j_r,i_l+i{j}_r,ij{j}_r)$

$iji$：$\max (i{j}_l+i_r,i_l{+}_j{i}_r,ij{i}_l,ij{i}_r)$

$jij$：$\max (j{i}_l+j_r,j_l+i{j}_r,ji{j}_l,ji{j}_r)$

$ijij$：$\max (i_l+ji{j}_r,i{j}_l+i{j}_r,ij{i}_l+j_r,iji{j}_l,iji{j}_r)$

$iijj$：$\max (iij{j}_l,ii{j}_l+j_r,i{i}_l+j{j}_r,i_l+ij{j}_r,iij{j}_r)$

最后答案为 $\max (ijij,iijj)$。

#include <bits/stdc++.h>
#define fp(i, a, b) for (int i = a, i##_ = (b) + 1; i < i##_; ++i)using namespace std;
using ll = int64_t;
const ll Inf = 1e18;
const int N = 2e5 + 5;
struct Data {ll ans, i, j, ii, ij, ji, jj, iij, iji, ijj, jij;Data(ll w = 0) { i = w, j = -w, ii = ij = ji = jj = iij = iji = ijj = jij = ans = -Inf; }Data operator+(const Data &b) const {Data a = *this, c;c.i = max(a.i, b.i);c.j = max(a.j, b.j);c.ii = max({a.ii, b.ii, a.i + b.i});c.ij = max({a.ij, b.ij, a.i + b.j});c.ji = max({a.ji, b.ji, a.j + b.i});c.jj = max({a.jj, b.jj, a.j + b.j});c.iij = max({a.iij, b.iij, a.ii + b.j, a.i + b.ij});c.iji = max({a.iji, b.iji, a.ij + b.i, a.i + b.ji});c.ijj = max({a.ijj, b.ijj, a.ij + b.j, a.i + b.jj});c.jij = max({a.jij, b.jij, a.ji + b.j, a.j + b.ij});c.ans = max({a.ans, b.ans, a.i + b.ijj, a.ii + b.jj, a.iij + b.j, a.i + b.jij, a.ij + b.ij, a.iji + b.j});return c;}
};
int n, q; ll a[N];
struct Seg {
#define lc (p << 1)
#define rc (p << 1 | 1)Data tr[N << 2];void up(int p) { tr[p] = tr[lc] + tr[rc]; }void build(int p, int L, int R) {if (L == R) return tr[p] = a[L], void();int m = (L + R) >> 1;build(lc, L, m), build(rc, m + 1, R), up(p);}Data qry(int p, int L, int R, int a, int b) {if (a <= L && R <= b) return tr[p];int m = (L + R) >> 1; Data w;if (b <= m) return qry(lc, L, m, a, b);if (a > m) return qry(rc, m + 1, R, a, b);return qry(lc, L, m, a, b) + qry(rc, m + 1, R, a, b);}
#undef lc
#undef rc
} T;
void Solve() {scanf("%d%d", &n, &q);fp(i, 1, n) scanf("%lld", a + i), a[i] *= a[i];T.build(1, 1, n);for (int l, r; q--;) {scanf("%d%d", &l, &r),printf("%lld\n", T.qry(1, 1, n, l, r).ans);}
}
int main() {int t = 1;scanf("%d", &t);while (t--)Solve();return 0;
}