2020 区域赛（南京）
亚洲区域赛（南京）
A: Ah, It's Yesterday Once More
打表题，我也不知道为什么
B：Baby's First Suffix Array Problem
神题
C：Certain Scientific Railgun
神题
D：Degree of Spanning Tree
给出一个图，求一棵生成树，它的所有节点的度数不超过 n/2。
结论指出：对于任何一棵树而言，在其结构中不会出现多于一个顶点具备超越半分位值（即高于 n/2）的数量特征。具体来说，在拥有 n 个顶点的一棵树中存在 n−1 条边线段连接这些顶点，在此过程中各顶点所贡献出的总次数合计为 2(n−1) 次次方程式的基本性质决定着这一现象的存在性与唯一性. 如果假定有两个或多个顶点达到了半分位值以上的高度那么其余所有顶点仅贡献一个单位次数的话那么总的次数将会超越 2(n−1) 的基础数值从而产生矛盾
因此没有度数大于n/2时直接输出生成树
否则，取度数大于n/2的节点为根，尝试使用非树上的边替换与根相连的边。
该生成树从根处断开而形成独立的部分（并查集用于维护）。接着枚举那些不在生成树上且不与根相连的边，并重新构建新的生成树结构。当我们选择一条新边时，在这种情况下会使得当前选中的节点及其相关联的部分减少一个连接的数量；同时连接这两个节点的一条新边会被添加进生成树中。如果这条新边被加入之后会导致超过n/2，则必须回退之前的步骤以恢复到之前的状态。
if(f(u)!= f(v)) {
d[u]++;
d[v]++;
int iny = ft[f(v)]; //和根连接的点
d[idx]--;
d[iny]--;
if(d[u]>n/2 || d[v]>n/2){ //加上非树边后，度数超过n/2
d[idx]++;
d[iny]++;
d[u]--;
d[v]--;
continue;
}
vis[iny]=1;
e[i].ok =1;
e[i^1].ok=1;
fa[f(v)] = f(u);
}E: Evil Coordinate
指定一个由U、D、L、R四个字符组成的字符串来表示机器人执行的动作序列。其中机器人最初位于坐标点(0,0)，而炸弹则位于位置(mx,my)。请问是否存在一种方式对上述提到的字符串进行重新排列组合后使用？这样处理后机器人沿着新的路径行走时不会经过点(mx,my)吗？
该字符串具有固定的终点。若起始点或终止点位于(mx, my)坐标，则问题无解。将上下左右方向统一考虑，并枚举行走路径的不同组合。若组合满足条件，则输出符合规范的结果。
F: Fireworks
制造烟花时，在每次完成k次操作后需等待m分钟对它们进行点亮测试。每个单独的烟花在被制造完成后都需要n分钟的时间才能完成点燃测试流程。当完成制造k个烟花并对其逐一测试后，在任何一个成功点亮的情况下就立即停止整个操作流程；如果全部未能成功点亮，则会继续进行后续的制造工作。
k次花火中至少一支被点亮的概率值为q=1-(1-p)^k，则其期望次数为1/q。总时耗等于k乘以n再加上m。
求k使得值最小。3分求极值
G: Go
神题
H: Harmonious Rectangle
给定一个n×m的矩阵A，在其每个元素位置上填充数字1、2、3。要求计算总共有多少种填充方式满足以下条件之一：第一种情况是在该矩阵中存在至少一对行坐标相同的两列（即(x₁, y₁)=(x₁, y₂)，且(x₂, y₁)=(x₂, y₂))；第二种情况是在该矩阵中存在至少一对列坐标相同的两行（即(x₁, y₁)=(x₂, y₁)，且(x₁, y₂)=(x₂, y²))）。
因为只关注一个矩阵的四个角点位置的变化情况, 所以对于由两个行和两个列组成的矩阵, 其计算公式为3^4=81种不同的填法方式。
假设有两行，则总共有3\times 3=9种可能的情况。换句话说，在某些情况下（如当列的数量达到或超过9时），必然与前面的某一列出现重复。
只有两列时同理。
则当n或者m>=9时，必存在题目要求的矩阵，则方案数为3^(n*m)。
当n < 9时（注意：原句中的"&&"可能是打字错误，默认处理为"且"），通过深度优先搜索（DFS）预计算得到结果：按行与列依次枚举每个单元格填充数字；若有已存在的符合条件的矩阵，则可以直接跳过并进行后续处理；进而直接计算剩余单元格的方案数量；剩余x个单元格，则每格有3种填充方式。
I: Interested in Skiing
考虑众多线段，在垂直方向上以速度vy运动的同时，在水平方向上具有速度分量v_x。我们关注是否存在一条路径从坐标点（0,-∞）到（0,+∞），该路径需避开所有给定的线段，并满足v_x大于某一临界值v_x_min；进而确定v_x_min的最大可能值。
在理想情况下，路线必然经过线段的两个端点。进而可预先计算出这两个端点之间的可达性。
若两个端点的斜率小于vy/vx，则无法行走。进而可对vxmin进行二分查找，并评估其可行性。
需要注意的是端点x≥m的部分是不可通行的区域，在规划路径时必须避免与线段相交，并确保人的横坐标x值始终小于m以避免越界
J: Just Another Game of Stones
给出n堆石头bi，然后有两个操作
1： 更新(l,r）为max(bi,x)
2：拿(l,r)中的石头和额外的一堆石头x，问有多少种先手必胜操作。
对于2：
根据Nim理论，在区间[l, r]上进行操作后得到结果为零时玩家处于劣势状态；反之，则需解决的问题即统计满足条件的i的数量，并计算表达式(b_i XOR k) XOR (b_l XOR b_{l+1} XOR ... XOR b_r) XOR x的结果是否等于零。
假设blb(l+1)...^b(r) = S. 则如果bi可以变成(bi^S),则异或和位0.
考虑什么情况下 b_i \oplus S \leq b_i 呢？如果 S 的最高有效位与 b_i 相同，则有 b_i \oplus S \leq b_i。这是因为假设 S 的最高有效位位于第 i 位置，在这种情况下，在高于 i 位置上可能有或没有 1 并且第 i 位置为 0 。因此，在执行异或操作后得到的结果将大于 S 。
最后就变成有多少个数的第i位是1.
可以用线段树去统计。
获取(l,r)区间内每一位的数量,接着将其与x中的每一位进行结合,具有最高数量的那个位即为最终结果
在处理更新操作时，在维护该线段的最大值的情况下（即当x超过当前最大值时），我们需要重新更新此线段；然而，在许多情况下这会导致在某些情况下会继续向下层次进行单节点的更新。
因此维护线段的最小值，次小值和最小值的个数。
当x介于最小值和次小值的情况下，更新最小值。
#include <string.h>
#include <assert.h>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <time.h>
#include <sstream>
#include <stdio.h>
#include <assert.h>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <stdlib.h>
#include <cassert>
//#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define clr(x) memset(x,0,sizeof(x))
#define _clr(x) memset(x,-1,sizeof(x))
#define fr(i,a,b) for(int i = a; i < b; ++i)
#define frr(i,a,b) for(int i = a; i > b; --i)
#define pb push_back
#define sf scanf
#define pf printf
#define mp make_pair
#define pir pair<int,int>
//#define N 2e5+10
#define N 600100
using namespace std;
//int mod = 998244353;
int mod = 1e9+7;
int get_min(int a, int b){
return a==-1? b: (b==-1?a:min(a,b));
}
ll get_min(ll a, ll b){
return a==-1? b: (b==-1?a:min(a,b));
}
int min_v[N];
int se_min_v[N];
int bit[N][32];
int num_min[N];
int n,q;
int a[N];
void update(int t, int val) {
for(int i = 0; i<30; ++i) {
bit[t][i] -= ((min_v[t]>>i)&1)*num_min[t];
}
min_v[t] = val;
for(int i = 0; i<30; ++i) {
bit[t][i] += ((min_v[t]>>i)&1)*num_min[t];
}
}
void push_down(int t) {
int lc = t<<1;
int rc = t<<1 | 1;
if(min_v[t] > min_v[lc]){
update(lc,min_v[t]);
}
if(min_v[t] > min_v[rc]) {
update(rc,min_v[t]);
}
}
void push_up(int t) {
int lc = t<<1;
int rc = t<<1 | 1;
for(int i = 0; i < 30; ++i) {
bit[t][i] = bit[lc][i] + bit[rc][i];
}
if(min_v[lc] > min_v[rc]) {
min_v[t] = min_v[rc];
num_min[t] = num_min[rc];
se_min_v[t] = min(se_min_v[rc], min_v[lc]);
}
else {
min_v[t] = min_v[lc];
num_min[t] = num_min[lc];
if(min_v[lc]==min_v[rc]){
num_min[t] += num_min[rc];
se_min_v[t] = min(se_min_v[lc],se_min_v[rc]);
}
else {
se_min_v[t] = min(se_min_v[lc], min_v[rc]);
}
}
}
void build(int t, int l, int r) {
if(l>r)return;
if(l==r) {
for(int i = 30; i >=0;--i) {
bit[t][i] = (a[l]>>i)&1;
}
min_v[t] = a[l];
se_min_v[t] = 1<<30;
num_min[t] = 1;
return;
}
int mid = (l+r)>>1;
build(t<<1, l, mid);
build(t<<1 | 1, mid+1, r);
push_up(t);
}
void add(int t, int l, int r, int ql, int qr, int x){
if(x <= min_v[t]){
return;
}
if(ql<=l && qr>=r && x<=se_min_v[t]){
update(t,x);
return;
}
push_down(t);
int mid = (l+r)>>1;
if(ql <= mid) add(t<<1, l, mid, ql, qr, x);
if(qr > mid) add(t<<1|1, mid + 1, r, ql,qr,x);
push_up(t);
}
int get_sum(int t, int l, int r,int ql, int qr){
if(l>r) return 0;
if(ql<=l && qr >=r) {
int ret = 0;
for(int i = 0; i < 30; ++i){
ret += (bit[t][i]&1)<<i;
}
return ret;
}
push_down(t);
int mid = (l+r)>>1;
int ret = 0;
if(ql<=mid){
ret ^= get_sum(t<<1,l, mid, ql,qr);
}
if(qr>mid){
ret ^= get_sum(t<<1|1, mid+1,r,ql,qr);
}
push_up(t);
return ret;
}
int get_bit(int t, int l, int r, int ql, int qr, int idx){
if(l>r) return 0;
if(ql<=l&&qr>=r){
return bit[t][idx];
}
push_down(t);
int mid = (l+r)>>1;
int ret = 0;
if(ql<=mid){
ret += get_bit(t<<1, l, mid, ql, qr, idx);
}
if(qr>mid){
ret += get_bit(t<<1|1, mid+1, r, ql, qr, idx);
}
push_up(t);
return ret;
}
int query(int l, int r, int x) {
int s = get_sum(1,1,n,l,r);
s^=x;
if(s==0)return 0;
int idx = 0;
for(int i = 30; i >=0;--i) {
if((s>>i)&1){
idx = i;
break;
}
}
return get_bit(1,1,n,l,r,idx) + ((x>>idx)&1);
}
int main(){
clr(min_v);
clr(se_min_v);
clr(bit);
clr(num_min);
cin>>n>>q;
for(int i = 1; i <=n; ++i) {
cin>>a[i];
}
build(1,1,n);
while(q--){
int op, l,r,x;
cin>>op>>l>>r>>x;
if(op==1)
add(1,1,n,l,r,x);
else {
cout<<query(l,r,x)<<endl;
}
}
}K: K Co-prime Permutation
构造一个数列ai，只有k个gcd(ai,i)==1.
由于只有k个，而且gcd(ai,ai)=ai，那么只需要用前k个。
另外注意到gcd(ai,ai+1)=1，那么只需要将前k个数shift一下就好了。
L: Let's Play Curling
给出两个序列ai,bi。求一个c，使得对于一个i和所有的j有
的i最多。
将b进行排序之后，在其后的每个a都满足条件的要求下，请计算位于两个相邻b之间的a的数量。（边界情况需特别处理）
M: Monster Hunter
给定一棵包含n个节点的树T，在T中要求消除所有顶点的存在。对于每个顶点v∈T，在其父顶点p(v)已被删除之前必须先删除v本身；每次消除操作的成本等于当前顶点v自身的权重a_v与其尚未被删除子顶点u的所有子顶点w∈child(u)中权重a_w之和即sub_a_v=∑_{w∈child(u)}a_w
一开始有k次机会消灭树上k个点。
主要基于树形动态规划的方法进行状态转移计算，在处理每个节点时会记录其状态信息。
n^2状态o(n)转移