A Tokitsukaze and a+b=n (easy)

简单题，做法很多。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 2e5 + 10;
int vis[N],n;
int main() {
	int T = read();
	while(T--) {
		memset(vis,0,sizeof(vis));
		n = read();
		int l = read(),r = read();
		for(int i = l;i <= r;i++) vis[i] = 1;
		l = read();r = read();
		int ans = 0;
		for(int i = l;i <= r;i++) {
			if(n - i <= 0) continue;
			ans += vis[n - i];
		}
		cout << ans << endl;
	}	
}

B Tokitsukaze and a+b=n (medium)

简单题，微微计算一下，画一个数轴理解。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 2e5 + 10;
int n;
int main() {
	int T = read();
	while(T--) {
		n = read();
		int l = read(),r = read();
		int L = read(),R = read();
		int t = l;
		l = n - r;r = n - t;
		if(l <= 0) l = 1;
//		cout << "ce: " << l << " " << r << endl;
		int ans = min(R,r) - max(l,L) + 1;
		if(ans < 0) ans = 0;
		cout << ans << endl;
	}	
}

C Tokitsukaze and a+b=n (hard)

中档题，根据 $AA$ 题的思路，我们其实就是要更好维护一下区间和，区间加，思路比较简单。我这里使用的是线段树，由于是有序组，最后答案乘 $22$ 。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 2e6 + 10;
const ll mod = 998244353;
const int m = 4e5 + 10;
ll tot,n;
ll t[N],ans,tag[N];
void add(int u,int l,int r,int L,int R) {
	if(L <= l && r <= R) {
		tag[u] += 1;
		t[u] += r - l + 1;
		t[u] %= mod;
		return ;
	}
	if(R < l || r < L) return;
	int mid = l + r >> 1;
	if(tag[u]) {
		tag[u << 1] += tag[u];tag[u << 1 | 1] += tag[u];
		t[u << 1] = (t[u << 1] + (mid - l + 1) * 1ll * tag[u] % mod) % mod;
		t[u << 1|1] = (t[u << 1|1] + (r - mid) * 1ll * tag[u] % mod) % mod;
		tag[u] = 0;
	}
	add(u << 1,l,mid,L,R);
	add(u << 1 | 1,mid + 1,r,L,R);
	t[u] = t[u << 1 | 1] + t[u << 1];
	t[u] %= mod;
}
ll ask(int u,int l,int r,int L,int R) {
	if(L <= l && r <= R) return t[u] % mod;
	if(R < l || r < L) return 0;
	int mid = l + r >> 1;
	if(tag[u]) {
		tag[u << 1] += tag[u];tag[u << 1 | 1] += tag[u];
		t[u << 1] = (t[u << 1] + (mid - l + 1) * 1ll * tag[u] % mod) % mod;
		t[u << 1|1] = (t[u << 1|1] + (r - mid) * 1ll * tag[u] % mod) % mod;
		tag[u] = 0;
	}
	ll res = (ask(u << 1,l,mid,L,R)+ask(u << 1 | 1,mid + 1,r,L,R)) % mod;
	t[u] = t[u << 1 | 1] + t[u << 1];
	t[u] %= mod;
	return res;
}
int main() {
	int T = 1;
	while(T--) {
		memset(t,0,sizeof(t));
		memset(tag,0,sizeof(tag));
		ans = 0;
		tot = read();n = read();
		for(int i = 1;i <= n;i++) {
			int l = read(),r = read();
			ans = (ans + ask(1,1,m,l,r)) % mod;		
			if(tot - l >= 1) {
				add(1,1,m,max(tot - r,1ll),tot - l);		
			}
		}
		cout << (ans * 2ll) % mod << endl;		
	}

}
 

D Tokitsukaze and Energy Tree

简单题，考虑到每一个节点在其父亲祖先节点算一次答案，所以我们用节点的深度排序，把最大深度的赋最大的值，然后计算和就行。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 2e5 + 10;
int n,si[N],val[N];
int main() {
	n = read();si[1] = 1;
	for(int i = 2;i <= n;i++) {
		int fa = read();
		si[i] = si[fa] + 1;
	}
	for(int i = 1;i <= n;i++) val[i] = read();
	sort(val + 1,val + 1 + n);
	sort(si + 1,si + 1 + n);
	ll ans = 0;
	for(int i = 1;i <= n;i++) {
		ans += si[i] * 1ll * val[i];
	}
	cout << ans << endl;
}

E Tokitsukaze and Function

中档题，很容易通过什么数学的分析，得到最值是在 $\sqrt{n}\backslash sqrt\{n\}$ 取得，但是这道题是只能取正整数，所以 $\lfloor \sqrt{n}\rfloor \backslash lfloor\; \backslash sqrt\{n\}\; \backslash rfloor$ 或者 $\lceil \sqrt{n}\rceil \backslash lceil\; \backslash sqrt\{n\}\; \backslash rceil$ 都有可能是最值。那么最值只会出现在 $\lfloor \sqrt{n}\rfloor ,\lceil \sqrt{n}\rceil ,L,R\backslash lfloor\; \backslash sqrt\{n\}\; \backslash rfloor,\backslash lceil\; \backslash sqrt\{n\}\; \backslash rceil,L,R$ 中。所以我们取其中的最小值，考虑到要求是最小的 $xx$ ，所以我们要求这个 $\{x\mid f(x)=f_{min}(x)\}\backslash \{x\backslash mid\; f(x)\; =\; f\_\{min\}(x)\backslash \}$ 中的最小值，我这里用的是倍增，二分也行。（代码用的不是向上取整，但是不影响正确性）

using namespace std;
#define pii pair<int,int>
#define ll long long
ll read() {
	ll x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
struct Node {
	ll pos,val;
}a[6];
ll n,L,R;
bool cmp(Node x,Node y) {
	return x.val < y.val;
}
ll f(ll x) {
	return n / x + x - 1;
}
int main() {
	int T = read();
	while(T--) {
		n = read();L = read();R = read();
		ll sqr = (sqrt(n) + 0.5),top = 0;
		a[++top] = (Node){L,f(L)};
		a[++top] = (Node){R,f(R)};
		if(L <= sqr && sqr <= R) a[++top] = (Node){sqr,f(sqr)};
		if(L <= sqr + 1 && sqr + 1 <= R)a[++top] = (Node){sqr + 1,f(sqr + 1)};
		sort(a + 1,a + top + 1,cmp);
		ll ans = a[1].pos,val = f(a[1].pos);
		for(ll i = 60;i >= 0;i--) {
			ll res = ans - (1ll << i);
//			cout << "val:: " << res <<"  pos:: "<<val<< endl;
			if(res < 1 || f(res) != val || res < L) continue;
			ans = res;
		}
		printf("%lld\n",ans);
	}
}

F Tokitsukaze and Gold Coins (easy)

简单题，考虑从起点和终点都来一次遍历，取交集。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 6e5 + 10;
int dp[N][4],n,k,vis[N][4];
int main() {
	int T = read();
	while(T--) {
		n = read();k = read();
		for(int i = 1;i <= k;i++) {
			int x = read(),y = read();
			vis[x][y] ^= 1;
			
		}
		dp[1][1] = 1;
		for(int i = 1;i <= n;i++) {
			for(int j = 1;j <= 3;j++) {
				if(!(dp[i][j] & 1) || vis[i][j]) continue;
				if(vis[i + 1][j] == 0 && i != n) dp[i + 1][j] |= 1;
				if(vis[i][j + 1] == 0 && j != 3) dp[i][j + 1] |= 1;
			}
		}
		if(dp[n][3] != 1) {
			cout << "0" << endl;
//			return 0;
		}
		else {
			dp[n][3] |= 2;
			for(int i = n;i >= 1;i--) {
				for(int j = 3;j >= 1;j--) {
					if(!(dp[i][j] & 2) || vis[i][j]) continue;
					if(vis[i - 1][j] == 0 && i != 1) dp[i - 1][j] |= 2;
					if(vis[i][j - 1] == 0 && j != 1) dp[i][j - 1] |= 2;
				}
			}
			int ans = 0;
			for(int i = 1;i <= n;i++) {
				for(int j = 1;j <= 3;j++) {
					if(dp[i][j] == 3) ans ++;
				}
			}
			cout << ans - 1 << endl;			
		}
//		cout << "SEE "<<endl;
		for(int i = 1;i <= n;i++) {
			for(int j = 1;j <= 3;j++) {
//				cout << dp[i][j] << " ";
				dp[i][j] = vis[i][j] = 0;
			}
//			cout << endl;
//			why？ 
		}
	}
}
/*
1
5 3
3 2
4 2
5 1
*/

G Tokitsukaze and Gold Coins (hard)

不会，留坑。

H Tokitsukaze and K-Sequence

中档题，贪心，每一次新加一个序列，我们都把现在第一序列中的每一个数字拿一个出来。然后记住当最大集合有 $22$ 个的时候，对答案的贡献是 $22$ 。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 1e5 + 100;
int n,T,a[N],b[N],vis[N];
vector<int> t[N];
int main() {
	int T = read();
	while(T--) {
		memset(vis,0,sizeof(vis));
		n = read();
		int Ans = 0;
		for(int i = 1;i <= n;i++) {
			a[i] = read();
			b[i] = a[i];
			vis[a[i]]++;
		}
		sort(b + 1,b + 1 + n);
		int len = unique(b + 1,b + 1 + n) - b - 1;
		for(int i = 1;i <= len;i++) t[vis[b[i]]].push_back(b[i]);
		int res = len;
		Ans += t[1].size();len -= t[1].size();
		printf("%d\n",Ans);
		for(int i = 2;i <= n;i++) {
			Ans += len;
			Ans += t[i].size();
			len -= t[i].size();
			printf("%d\n",Ans);
		}
		for(int i = 1;i <= n;i++) t[i].clear();
	}
}

I Tokitsukaze and Musynx

中档题，对整个序列做差分，每一个数字能改变值的次数是 $44$ 次，所以离散化一下，然后从左到右依次遍历取 $\max \backslash max$ 。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
map<ll,ll> s;
ll val[6],n,c[6],a[200100],ans,sum;
int main() {
	int T = read();
	while(T--) {
		n = read();
		s.clear();
		for(int i = 1;i <= n;i++) a[i] = read();
		for(int i = 1;i <= 4;i++) c[i] = read();
		for(int i = 1;i <= 5;i++) val[i] = read();
		ans = sum = n * val[1];
		for(int i = 1;i <= n;i++) {
			for(int j = 1;j <= 3;j++) {
				s[c[j] - a[i]] += val[j + 1] - val[j];
			}
			s[c[4] + 1 - a[i]] += val[5] - val[4];
		}
		for(auto it : s) {
			sum += it.second;
			ans = max(sum,ans);
		}
		cout << ans << endl;
	}
}

J Tokitsukaze and Sum of MxAb

简单题，发现无论是 $++,+-,--++,+-,--$ $f(a,b)f(a,b)$ 的值都是两个数字绝对值之和。然后考虑每个次数的出现次数是 $n\times 2n\; \backslash times2$ 。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
ll a,n;
int main() {
	int T = read();
	while(T--) {
		n = read();a = 0;
		for(int i = 1;i <= n;i++) a = a + abs(read());
		cout << (ll)a * n * 2  << endl;
	}	
}

K Tokitsukaze and Synthesis and Traits

中档题，应该是根号分治，但是我比赛时候没写出来。然后我直接考虑离线答案，开一个桶记录一下。（感觉复杂度还挺低的）

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 2e5 + 10;
vector<int> G[N],vis[N];
vector<pii> e;
int n,m,q,ans[N];
int main() {
	n = read();m = read();q = read();
	for(int i = 1;i <= m;i++) {
		int a = read(),b = read();
		G[a].push_back(b);
		G[b].push_back(a);
		e.push_back(pii(a,b));
	}
	for(int Id = 1;Id <= q;Id++) {
		int k = read();
		for(int i = 1;i <= k;i++) {
			int a = read();
			vis[a].push_back(Id);
		}
	}
	for(int i = 1;i <= n;i++) sort(vis[i].begin(),vis[i].end());
	for(int i = 0;i < m;i++) {
		int x = e[i].first,y = e[i].second;
		int l = 0,r = 0;
		while(l < vis[x].size() && r < vis[y].size()) {
			if(vis[x][l] == vis[y][r]) ans[vis[x][l]]++,l++,r++;
			else if(vis[x][l] < vis[y][r]) l++;
			else r++;
		}
	}
	for(int i = 1;i <= q;i++) printf("%d\n",ans[i]);
}

L Tokitsukaze and Three Integers

简单题，容斥一下。减去两个相同，三个相同的。用桶记录答案就好。

using namespace std;
#define pii pair<int,int>
#define ll long long
ll read() {
	ll x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 5050;
ll n,p,a[N],vis[N],ans[N];
ll mul(ll x,ll y) {return (1ll * x * y) % p;}
ll add(ll x,ll y) {return (x + y) % p;}
int main() {
	n = read();p = read();
	for(int i = 1;i <= n;i++) {
		a[i] = read();
	}
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= n;j++) {
			vis[mul(a[i],a[j])]++;
		}
	}
	for(int i = 1;i <= n;i++) {
		for(int v = 0;v < p;v++) {
			ans[add(v,a[i])] += vis[v];
		}
	}
	//12 相同
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= n;j++) {
			if(i == j) continue;
			ans[add(mul(a[i],a[i]),a[j])]--;
		}
	}
	//(1 or 2) 3 相同
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= n;j++) {
			if(i == j) continue;
			ans[add(mul(a[i],a[j]),a[i])]-=2;
		}
	}
	// 123 相同 
	for(int i = 1;i <= n;i++) ans[add(mul(a[i],a[i]),a[i])]--;
	for(int i = 0;i < p;i++) cout << ans[i] << " ";
	cout << endl;
}