注意，题目顺序可能有调整

A

一个经典的转化：左括号看成 $+1$，右括号看成 $-1$，括号串合法当且仅当所有前缀和 $\ge 0$，且所有数的和 $=0$。

考虑 $dp(i,j)$ 表示，前 $i$ 个字符，目前前缀和为 $j$ 的方案数。转移：

• $dp(i,j) \rightarrow dp(i+1,j)$ 表示第 $i$ 个字符在子序列中不选。
• $dp(i,j) \rightarrow dp(i+1,j-1)$（要求 $j \gt 0$，且 $s_{i+1}$ 为 ) 或 ?），表示第 $i$ 个字符选，且其为 )
• $dp(i,j) \rightarrow dp(i+1,j+1)$（要求 $s_{i+1}$ 为 ( 或 ？），表示第 $i$ 个字符选，且其为 (

答案即为 $dp(n,0)$，复杂度 $O(n^2)$。

/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int n;
char s[5005];
int dp[5005][5005];
void solve()
{
	cin>>n;
	cin>>(s+1);
	dp[0][0]=1;
	for(int i=0;i<n;i++) for(int j=0;j<=i;j++)
	{
		dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
		if(s[i+1]!='('&&j) dp[i+1][j-1]=(dp[i+1][j-1]+dp[i][j])%mod;
		if(s[i+1]!=')') dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j])%mod; 
	}
	cout<<dp[n][0]<<"\n";
}
signed main()
{
	freopen("bracket.in","r",stdin);
	freopen("bracket.out","w",stdout);
//	ios::sync_with_stdio(0);
//	cin.tie(0);
	int _=1;
//	cin>>_;
	while(_--) solve();
	return 0;
} 

B

注意到 $m$ 十分的大， 如果把所有武将都全部升级肯定最优，因为每个武将都可以产生大于升级它所需代价的收益。

正着算不是很好算，我们可以将全部收益减去升级之前的收益，也就是说如果一个装置在第 $j$ 分钟成功升了一级，那么就从总收益中减去 $j$ 的收益。

题意转化为 $n$ 个数组 $a_i$，要将所有元素重排进 长度为 $\sum k_i$ 数组 $b$，使得 $b$ 数组中的元素顺序满足在 $a_i$ 数组中的顺序关系，并且使得 $b$ 数组的前缀和的和最小。

如果不考虑 $a$ 数组的限制关系，显然是直接将所有数排个序，可以使前缀和的和最小。

更一般的，我们设想 $b$ 数组中的两段数，第一段数排在第二段前的充要条件，显然是第一段数的平均值小于第二段数。

所以我们要做的，是每次把所有 $a_i$ 中最小平均值的一段数拿出来，放到 $b$ 数组中去。

将每个 $a$ 数组提前分好段，这样的段在每个 $a$ 数组中的平均值都是单调递增的，就转化为所有元素都递增的的情况，直接排序就好了。

怎么分段呢？我们每次在当前段加入一个数，如果这一段平均值变小，就合并，否则继续。但这样的数列 $9,8,7,6,10,1,1,1$ 前四个数的平均值大于后四个数，还要再做一次，这样最劣要从前往后做 $n$ 次，复杂度 $O(n^2)$。

我们发现，当加入一个数时，如果平均值不变小，就可以和上一段比，如果上一段平均值比这一段平均值大，那么往前合并，然后将下一个数当做一个新段。因为每合并一次就会少一段，所以这这样做 $O(n)$ 的。

瓶颈在排序，复杂度 $O(nlogn)$。

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'
// #define int long long
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double db;
typedef pair<int, int> pii;

const int N = 2e6+5;
const int inf = 1e9;
const int p = 1e9+7;

ll n,m;
int nxt[N], pre[N], hd[N], tot;

struct node{
    ll len, s, cs;
    bool is;
}a[N];
signed main(){
    freopen("dog.in","r",stdin);
    freopen("dog.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
    cin >> n >> m;

    ll cnt = 0, k, val;
    for (int i = 1; i <= n; i++){
        cin >> k;
        hd[++tot] = ++cnt; a[cnt].is = 1;
        nxt[cnt] = cnt+1;

        for (int j = 1; j <= k; j++){
            cin >> val;
            a[++cnt] = {1, val, val,0};
            pre[cnt] = cnt-1;
            if (j < k) nxt[cnt] = cnt+1;
        }
    }
    auto get = [&](node x, node y){
        node t = {1,0,0,0};
        t.s = x.s+y.s;
        t.cs = x.cs+x.s*y.len+y.cs;
        t.len = x.len+y.len;
        return t;
    };
    auto merge = [&](int x, int y){
        a[x] = get(a[x],a[y]);
        nxt[x] = nxt[y]; pre[nxt[y]] = x;
        a[y].is = 1;
    };

    for (int i = 1; i <= tot; i++){
        for (int j = nxt[hd[i]]; j; j = nxt[j]){
            if (nxt[j] && a[j].s >= a[j].len*a[nxt[j]].s){
                merge(j, nxt[j]);
            }
            int jj = j;
            while (pre[jj] && !a[pre[jj]].is){
                if (a[pre[jj]].s*a[jj].len >= a[jj].s*a[pre[jj]].len) merge(pre[jj], jj);
                else break;
                jj = pre[jj];
                
            }
        }
    }

    sort(a+1,a+cnt+1,[&](node a, node b){
        if (a.is != b.is) return a.is < b.is;
        return a.s*b.len < b.s*a.len;
    });

    node t = {0,0,0,0};
    for (int i = 1; !a[i].is; i++){
        t = get(t,a[i]);
    }
    cout << (cnt-n)*m-t.cs << endl;
    return 0;
}

C

首先可以 $O(n^3)$，暴力枚举区间左右端点再暴力 check，check 部分用 ST 表预处理区间 $\min$ 和区间 $\max$ 即可 $O(n^2)$。

特殊性质是序列前一部分单调不降，后一部分单调不增。容易发现区间在其中一部分的时候是单调的，端点处一定为最值，不符合条件；跨过两部分时，最小值一定在最左端或最右端取到，也不符合条件。因此答案全为 $0$。

我们考虑算每个左端点的答案（右端点是类似的）。使一个 $i$ 能成为合法左端点的 $j$ 必须满足 $(i,j]$ 中出现了大于 $a_i$ 的数和小于 $a_i$ 的数，记 $mr_i$ 和 $nr_i$ 为 $i$ 后面第一个大于 $a_i$ 和小于 $a_i$ 的元素的下标，令 $R_i = \max\{mr_i,nr_i\}$，则 $j$ 需要满足 $j \ge R_i$。

此外，$i$ 不一定能满足 $a_j$ 不是区间最值的条件，对称地，记 $ml_j$ 和 $rl_j$ 为 $j$ 前面第一个大于 $a_j$ 和小于 $a_j$ 的元素的下标，令 $L_j = \min\{ml_j,nl_j\}$，$j$ 需要满足 $i\ge L_j$。

以上的 $mr_i,nr_i,ml_j,nl_j$ 均可用单调栈线性求出，那么 $i$ 的答案为满足 $L_j \le i$ 且 $j\le R_i$ 的 $j$ 的个数，经典二维数点，可以用树状数组完成。该做法有 $O(n\log n)$ 的时间复杂度。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define gc getchar
#define pc putchar
#define fs first
#define sc second
using namespace std;

ll read()
{
	ll x=0,f=1;
	char ch=gc();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=gc();
	}
	while(ch>='0'&&ch<='9')
		x=x*10+(ch^48),ch=gc();
	return x*f;
}
void print(ll x)
{
	if(x<0)pc('-'),x=-x;
	if(x>9)print(x/10);
	pc(x%10+48);
}

const int N=1e6+5;
int n,id,v[N],f[N],g[N],f1[N],f2[N],g1[N],g2[N],st[N],top,ans[N];
struct node{
	int x,y;
}p1[N],p2[N];

bool cmp(node i,node j){
	return i.y<j.y;
}

struct BIT
{
	#define lowbit(x) (x&(-x))
	
	int sum[N];
	void update(int x)
	{
		while(x<=n)
			sum[x]++,x+=lowbit(x);
	}
	int query(int x)
	{
		int res=0;
		while(x)
			res+=sum[x],x-=lowbit(x);
		return res;
	}
}T1,T2;

int main()
{
	freopen("interval.in","r",stdin);
	freopen("interval.out","w",stdout);
	
	n=read(),id=read();
	
	for(int i=1;i<=n;i++)
	{
		v[i]=read();
		f1[i]=f2[i]=n+1,g1[i]=g2[i]=0;
	}
	
	for(int i=1;i<=n;i++)
	{
		while(top&&v[i]<v[st[top]])
			f1[st[top--]]=i;
		st[++top]=i;
	}
	top=0;
	for(int i=1;i<=n;i++)
	{
		while(top&&v[i]>v[st[top]])
			f2[st[top--]]=i;
		st[++top]=i;
	}
	
	top=0;
	for(int i=n;i>=1;i--)
	{
		while(top&&v[i]<v[st[top]])
			g1[st[top--]]=i;
		st[++top]=i;
	}
	top=0;
	for(int i=n;i>=1;i--)
	{
		while(top&&v[i]>v[st[top]])
			g2[st[top--]]=i;
		st[++top]=i;
	}
	
	for(int i=1;i<=n;i++)
	{
		f[i]=max(f1[i],f2[i]);
		g[i]=min(g1[i],g2[i]);
		p1[i]={i,g[i]},p2[i]={i,f[i]};
	}
	
	sort(p1+1,p1+1+n,cmp);
	for(int i=n,j=n;i>=1;i--)
	{
		while(j>=1&&i<=p1[j].y)
			T1.update(p1[j--].x);
		ans[i]=n-j-T1.query(f[i]-1);
	}
	for(int i=1;i<=n;i++)
		print(ans[i]),pc(' ');
	pc('\n');
	
	sort(p2+1,p2+1+n,cmp);
	for(int i=1,j=1;i<=n;i++)
	{
		while(j<=n&&i>=p2[j].y)
			T2.update(p2[j++].x);
		ans[i]=T2.query(g[i]);
	}
	for(int i=1;i<=n;i++)
		print(ans[i]),pc(' ');
	
	return 0;
}

D

将所有数按模 $4$ 意义分组，令 $S_0,S_1,S_2,S_3$ 表示四个集合。

考虑全是偶数的情况，此时一定有解，因为两个 $S_0$ 中的元素，或两个 $S_2$ 中的元素，对其操作之后一定产生一个偶数，不断这样操作，不能操作的时候要么已经操作完，要么 $|S_0|=|S_2|=1$，此时将剩余两个数操作即可。全是奇数同理。

对于一般情况，先要证明一个引理：

• 若 $|S_0|,|S_2| \ge 1$ 或 $|S_1|,|S_3| \ge 1$，则能构造出解。

证明：以 $|S_0|,|S_2| \ge 1$ 为例，保留两个集合各一个元素 $x_0,x_2$，将剩下的奇数和剩下的偶数随便操作，可能会得到：

• 剩余一个奇数：此时操作 $x_0,x_2$，得到奇数，和剩下的奇数操作。
• 剩余一个偶数：偶数要么属于 $|S_0|$，要么属于 $|S_2|$，取两个属于相同集合的元素操作，得到偶数，再和剩下的偶数操作。
• 剩余一个奇数和一个偶数：将所有数设成 $4a+b$ 的形式：不妨设我们有四个数：$4a_1+0,4a_2+0,4a_3+2,4a_4+1$。
  • 可以操作 $4a_2+0,4a_3+2$，得到 $2(a_2+a_3)+1$，然后和 $4a_4+1$ 操作得到 $a_2+a_3+2a_4+1$，若 $a_2+a_3$ 为奇数，则可以和 $4a_1+0$ 操作构造出解。
  • 若将上述方法的第一步换成操作 $4a_1+0,4a_3+2$，则若 $a_1+a_3$ 为奇数，则可以和 $4a_3+0$ 构造出解。
  • 令 $a_1,a_2$ 奇偶性相同，操作 $4a_1+0,4a_2+0$，得到 $2(a_1+a_2)$，其一定属于 $S_0$，可以用上文“剩余一个奇数”的方式处理。

如果我们能构造出一个 $S_0$ 中的元素和一个 $S_2$ 中的元素，或者构造出一个 $S_1$ 中的元素和一个 $S_3$ 中的元素，随便操作后暴力解剩下的四个数，问题得以解决。

以 $S_0$ 和 $S_2$ 为例，找出所有偶数中最低的二进制位 $d$ ，满足所有数在这一位上不全部相同。任意找出两个不相同的数，不妨设两个数为：$a_12^{d+1}+b$ 和 $a_22^{d+1}+2^d+b$，操作这两个数，得到 $(a_1+a_2)2^d+2^{d-1}+b$，此时第 $d-1$ 位一定改变，将 $d$ 减去 $1$ 继续进行同样的过程，注意先判断数够不够。

复杂度 $O(n \log A)$，$A$ 是值域。

/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
mt19937 rnd(time(0));
struct Random_array
{
	int a[2000005],in[2000005],n,has;
	void init()
	{
		n=has=0;
	}
	void rebuild()
	{
		int j=0;
		for(int i=1;i<=n;i++) if(in[i]) j++,a[j]=a[i],in[j]=1;
		n=has=j;
	}
	void add(int x)
	{
		a[++n]=x,has++,in[n]=1;
	}
	int query()
	{
		int x=1+rnd()%n;
		while(!in[x]) x=1+rnd()%n;
		has--,in[x]=0;
		int res=a[x];
		if(has<n/2) rebuild();
		return res;
	}
}O,E;
void random_small(vector <int> vec)
{
	while(1)
	{
		O.init(),E.init();
		for(int i=0;i<vec.size();i++)
		{
			if(vec[i]%2==0) E.add(vec[i]);
			else O.add(vec[i]);
		}
		vector <pii > ans;
		ans.clear();
		while(O.has+E.has>=2)
		{
			if(O.has==1&&E.has==1) break;
			int tag=-1;
			if(O.has>=2&&E.has>=2) tag=rnd()%2;
			else if(O.has>=2) tag=0;
			else tag=1;
			if(tag==0)
			{
				int u=O.query();
				int v=O.query();
				ans.pb(mp(u,v));
				if(((u+v)/2)%2==1) O.add((u+v)/2);
				else E.add((u+v)/2);
			}
			else
			{
				int u=E.query();
				int v=E.query();
				ans.pb(mp(u,v));
				if(((u+v)/2)%2==1) O.add((u+v)/2);
				else E.add((u+v)/2);
			}
		}
		if(O.has+E.has==1)
		{
			for(int i=0;i<ans.size();i++) cout<<ans[i].fi<<" "<<ans[i].se<<"\n";
			return;
		}
	}
}
int construct_same(vector <int> vec)
{
	vector <int> v[2];
	v[0].clear(),v[1].clear();
	for(int i=0;i<vec.size();i++) v[(vec[i]%4)/2].pb(vec[i]);
	while(v[0].size()+v[1].size()>=2)
	{
		if(v[0].size()>=2)
		{
			int x=v[0][v[0].size()-1];
			v[0].pop_back();
			int y=v[0][v[0].size()-1];
			v[0].pop_back();
			cout<<x<<" "<<y<<"\n";
			x=(x+y)/2;
			v[(x%4)/2].pb(x);
		}
		else if(v[1].size()>=2)
		{
			int x=v[1][v[1].size()-1];
			v[1].pop_back();
			int y=v[1][v[1].size()-1];
			v[1].pop_back();
			cout<<x<<" "<<y<<"\n";
			x=(x+y)/2;
			v[(x%4)/2].pb(x);
		}
		else 
		{
			cout<<v[0][0]<<" "<<v[1][0]<<"\n";
			return (v[0][0]+v[1][0])/2;
		}
	}
	return (v[0].size()?v[0][0]:v[1][0]);
}
pii find_diff(vector <int> v,int i)
{
	int f1=0,f2=0;
	for(int j=0;j<v.size();j++)
	{
		if(v[j]&(1LL<<i)) f1=j;
		else f2=j;
	}
	return mp(f1,f2);
}
int n,a[2500005];
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	vector <int> v[2];
	v[0].clear(),v[1].clear();
	for(int i=1;i<=n;i++) v[a[i]%2].pb(a[i]);
	if(v[0].size()==n) 
	{
		construct_same(v[0]);
		return;
	}
	if(v[1].size()==n)
	{
		construct_same(v[1]);
		return;
	}
	int min_d=inf;
	for(int i=1;i<60;i++)
	{
		int f1=0,f2=0;
		for(int j=0;j<v[0].size();j++)
		{
			if(v[0][j]&(1LL<<i)) f1=1;
			else f2=1;
		}
		if(f1&&f2)
		{
			min_d=i;
			break;
		} 
	}
//	cout<<v[0].size()<<" "<<min_d<<"\n";
	if(v[0].size()>=min_d+1)
	{
		for(int i=min_d;i>=2;i--)
		{
			pii t=find_diff(v[0],i);
			if(t.fi>t.se) swap(t.fi,t.se);
			int x=v[0][t.fi],y=v[0][t.se];
			cout<<x<<" "<<y<<"\n";
			v[0].erase(v[0].begin()+t.fi),v[0].erase(v[0].begin()+t.se-1);
			v[0].pb((x+y)/2);
		}
		pii t=find_diff(v[0],1);
		if(t.fi>t.se) swap(t.fi,t.se);
		int x=v[0][t.fi],y=v[0][t.se];
//		cout<<x<<" "<<y<<"\n";
		v[0].erase(v[0].begin()+t.fi),v[0].erase(v[0].begin()+t.se-1);
		int z=(v[0].size()?construct_same(v[0]):-1);
		int w=construct_same(v[1]);
		vector <int> vec;
		vec.clear();
		vec.pb(x),vec.pb(y),vec.pb(w);
		if(z!=-1) vec.pb(z);
		random_small(vec);
		return;
	}
	swap(v[0],v[1]);
	min_d=inf;
	for(int i=1;i<60;i++)
	{
		int f1=0,f2=0;
		for(int j=0;j<v[0].size();j++)
		{
			if(v[0][j]&(1LL<<i)) f1=1;
			else f2=1;
		}
		if(f1&&f2)
		{
			min_d=i;
			break;
		} 
	}
//	cout<<"... "<<v[0].size()<<" "<<min_d<<"\n";
	if(v[0].size()>=min_d+1)
	{
		for(int i=min_d;i>=2;i--)
		{
			pii t=find_diff(v[0],i);
			if(t.fi>t.se) swap(t.fi,t.se);
			int x=v[0][t.fi],y=v[0][t.se];
			cout<<x<<" "<<y<<"\n";
			v[0].erase(v[0].begin()+t.fi),v[0].erase(v[0].begin()+t.se-1);
			v[0].pb((x+y)/2);
		}
		pii t=find_diff(v[0],1);
		if(t.fi>t.se) swap(t.fi,t.se);
		int x=v[0][t.fi],y=v[0][t.se];
//		cout<<x<<" "<<y<<"\n";
		v[0].erase(v[0].begin()+t.fi),v[0].erase(v[0].begin()+t.se-1);
		int z=(v[0].size()?construct_same(v[0]):-1);
		int w=construct_same(v[1]);
		vector <int> vec;
		vec.clear();
		vec.pb(x),vec.pb(y),vec.pb(w);
		if(z!=-1) vec.pb(z);
		random_small(vec);
		return;
	}
	cout<<"-1\n";
}
signed main()
{
	freopen("meow.in","r",stdin);
	freopen("meow.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
	cin>>_;
	while(_--) solve();
	return 0;
}