Educational Codeforces Round 166 (Rated for Div. 2) (C、D）

1976C - Job Interview 

        题意：

        思路：考虑求出如果多一个程序员，那么整个序列该怎么选，多一个测试员，整个序列该怎么选。那么若第个人原先是程序员，那么他不来面试以后后面的所有人选择情况就是多一个程序员的情况。同理，若第个人原先是测试员，那么他不来面试以后后面所有人选择情况就是多一个测试员的选择情况。然后考虑用前缀和来快速求解。

// Problem: C. Job Interview
// Contest: Codeforces - Educational Codeforces Round 166 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1976/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
 
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
#define int long long
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}
 
LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
void solve() 
{
	int n , m;
	cin >> n >> m;
	int a[n + m + 1];
	int b[n + m + 1];
	int res1 = n , res2 = m;
	for(int i = 0 ; i < n + m + 1; i ++){
		cin >> a[i];
	}
	for(int i = 0 ; i < n + m + 1; i ++){
		cin >> b[i];
	}
	vector<int>val(n + m + 1 , 0);
	vector<int>ans(n + m + 1 , 0);
	vector<int>cntt(n + m + 1 , 0);//正常分配
	vector<int>cntt1(n + m + 1 , 0);//前面少一个程序员
	vector<int>cntt2(n + m + 1 , 0);//前面少一个测试员
	int cnt = 0;
	for(int i = 0 ; i < n + m ; i ++){
		if(a[i] > b[i] && res1 > 0){
			cnt += a[i];
			res1 --;
			val[i] = 1;
		}
		else if(a[i] > b[i]){
			cnt += b[i];
			res2 --;
			val[i] = 2;
		}
		if(a[i] < b[i] && res2 > 0){
			cnt += b[i];
			res2--;
			val[i] = 2;
		}
		else if(a[i] < b[i]){
			cnt += a[i];
			res1--;
			val[i] = 1;
		}
		cntt[i] = cnt;
	}
	ans[n + m] = cnt;
	res1 = n + 1 , res2 = m;
	cnt = 0;
	for(int i = 0 ; i < n + m + 1 ; i ++){
		if(a[i] > b[i] && res1 > 0){
			cnt += a[i];
			res1 --;
		}
		else if(a[i] > b[i]){
			cnt += b[i];
			res2 --;
		}
		if(a[i] < b[i] && res2 > 0){
			cnt += b[i];
			res2--;
		}
		else if(a[i] < b[i]){
			cnt += a[i];
			res1--;
		}
		cntt1[i] = cnt;		
	}
	res1 = n , res2 = m + 1;
	cnt = 0;
	for(int i = 0 ; i < n + m + 1 ; i ++){
		if(a[i] > b[i] && res1 > 0){
			cnt += a[i];
			res1 --;
		}
		else if(a[i] > b[i]){
			cnt += b[i];
			res2 --;
		}
		if(a[i] < b[i] && res2 > 0){
			cnt += b[i];
			res2--;
		}
		else if(a[i] < b[i]){
			cnt += a[i];
			res1--;
		}
		cntt2[i] = cnt;		
	}
	for(int i = 0 ; i < n + m ; i ++){
		int anss = 0;
		if(val[i] == 1){
			anss += cntt1[n + m] - cntt1[i];
		}
		else if(val[i] == 2){
			anss += cntt2[n + m] - cntt2[i];
		}
		if(i != 0)
			anss += cntt[i - 1];
		cout << anss << " ";
	}
	cout << ans[n + m] << endl;
}            
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

 1976D - Invertible Bracket Sequences

        题意：

        思路：我们统计序列前个有多少个左括号是剩余的，然后思考的选择有何特征：可以发现，若第位之前所剩余的左括号跟第位之前所剩余的左括号数量一样，那么这个区间就可能被选择，否则一定不会被选择。

        因此我们将剩余左括号数量相同的位置放一起，然后考虑其区间能否真的被选中。通过观察可以发现：若之间位置的剩余左括号数量小于等于第位之前所剩余的左括号的两倍，那么这个区间就可以被选中，因此本题转换成RMQ问题。

        光这样的复杂度是的，然后发现在枚举位置时，随着起始位置的增大，末尾位置也一定是非递减的，因此用双指针可以将复杂度变为

// Problem: D. Invertible Bracket Sequences
// Contest: Codeforces - Educational Codeforces Round 166 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1976/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
 
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
#define int long long
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}
 
LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
int Max[N][21];
int Min[N][21];
struct ST{
	void init(){
		for(int i = 1 ; i <= n ; i ++){
			Max[i][0] = a[i];
			Min[i][0] = a[i];
		}
	}
	void work(){
	    for(int j = 1;j <= 21;j++)
	        for(int i = 1;i + (1 << j) - 1 <= n ; i++){	            
	        	Max[i][j] = max(Max[i][j - 1] , Max[i + (1 << (j - 1))][j - 1]);
	            Min[i][j] = min(Min[i][j - 1] , Min[i + (1 << (j - 1))][j - 1]);	
	        }
	}
	int QueryMax(int l,int r)
	{
	    int k = log2(r-l+1); 
	    return max(Max[l][k],Max[r-(1<<k)+1][k]);//把拆出来的区间分别取最值 
	}	
	int QueryMin(int l , int r){
	    int k = log2(r-l+1); 
	    return min(Min[l][k],Min[r-(1<<k)+1][k]);//把拆出来的区间分别取最值 		
	}
};
void solve() 
{
	//左括号等于右括号且
	string s;
	cin >> s;
	s = "0" + s;
	int len = s.size();
	n = len + 5;
	a[0] = 0;
	vector<int>st[len];
	for(int i = 1 ; i < len ; i++){
		if(s[i] == '('){
			a[i] = a[i - 1] + 1;
		}
		else{
			a[i] = a[i - 1] - 1;
		}
		st[a[i]].pb(i);
	}
	//RMQ
	ST stb;
	stb.init();
	stb.work();
	int cnt = 0;
	for(int i = 1 ; i < len ; i ++){
		if(st[i].size() <= 1)
			continue;
		int len = st[i].size();
		int r = 0;
		for(int l = 0 ; l < len ; l ++){
			if(r == len){
				cnt += (r - l - 1);
				continue;
			}
			int left = st[i][l] , right = st[i][r];
			while(r < len && stb.QueryMax(left , right) <= i * 2){
				r++;
				if(r == len){
					break;
				}
				right = st[i][r];
			}
			cnt += (r - l - 1);
		}
	}
	cout << cnt << endl;
}            
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}