差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:farmer_john:jjleo:2020.05.16-2020.05.22 [2020/05/22 22:12]
jjleo [CF455D]
+++ 2020-2021:teams:farmer_john:jjleo:2020.05.16-2020.05.22 [2020/06/25 23:06] (当前版本)
jjleo ↷ 页面2020-2021:teams:farmer_john:2020.05.16-2020.05.22被移动至2020-2021:teams:farmer_john:jjleo:2020.05.16-2020.05.22
@@ 行 76: / 行 76: @@
 	printf("%d", f[1][1]);
 } </code></hidden>
-=====CF455D=====
+=====CF300D=====
 卷积dp。
 <hidden><code cpp>#include <bits/stdc++.h>
@@ 行 112: / 行 112: @@
 }</code></hidden>
 =====CF319C=====
-<hidden><code cpp></code></hidden>
+斜率优化。
+<hidden><code cpp>#include <bits/stdc++.h>
+#define maxn 100086
+using namespace std;
+typedef long long ll;
+int n;
+ll a[maxn], b[maxn], f[maxn];
+int q[maxn], l, r;
+inline double k(int i, int j){
+	return 1.0 * (f[i] - f[j]) / (b[j] - b[i]);
+}
+int main(){
+	scanf("%d", &n);
+	for(int i = 1;i <= n;i++) scanf("%lld", &a[i]);
+	for(int i = 1;i <= n;i++) scanf("%lld", &b[i]);
+	f[1] = 0, q[0] = 1;
+	for(int i = 2;i <= n;i++){
+		while(l < r && k(q[l], q[l + 1]) <= a[i]) ++l;
+		f[i] = f[q[l]] + a[i] * b[q[l]];
+		//printf("%d %d %lld--\n", i, q[l], f[i]);
+		while(l < r && k(q[r], q[r - 1]) >= k(q[r], i)) --r;
+		q[++r] = i;
+	}
+	printf("%lld", f[n]);
+}</code></hidden>
+=====CF455D=====
+数据结构，分块+deque。
+<hidden><code cpp>#include <bits/stdc++.h>
+#define maxn 100086
+#define maxm 320
+using namespace std;
+int f[maxm][maxn];
+int n, sn;
+int opt, l, r, k;
+int m, x;
+deque<int> q[maxm];
+int lastans;
+int main(){
+	scanf("%d", &n), sn = (int)sqrt(n);
+	for(int i = 1;i <= n;i++){
+		scanf("%d", &x);
+		int ii = (i - 1) / sn;
+		q[ii].push_back(x), ++f[ii][x];
+	}
+	scanf("%d", &m);
+	while(m--){
+		scanf("%d", &opt);
+		if(opt == 1){
+			scanf("%d%d", &l, &r);
+			l = (l + lastans - 1) % n + 1, r = (r + lastans - 1) % n + 1;
+			if(l > r) swap(l, r);
+			int ll = (l - 1) / sn, rr = (r - 1) / sn, li = (l - 1) % sn, ri = (r - 1) % sn;
+			//printf("%d %d %d %d--\n", ll, rr, li, ri);
+			if(ll == rr){
+				int x = q[ll][ri];
+				q[ll].erase(q[ll].begin() + ri);
+				q[ll].insert(q[ll].begin() + li, x);
+			}else{
+				int x = q[ll].back();q[ll].pop_back(), --f[ll][x];
+				for(int i = ll + 1;i < rr;i++){
+					q[i].push_front(x), ++f[i][x];
+					x = q[i].back(), q[i].pop_back(), --f[i][x];
+				}
+				q[rr].push_front(x), ++f[rr][x];
+				x = q[rr][ri + 1], --f[rr][x], q[rr].erase(q[rr].begin() + ri + 1);//debug:已经pushfront了所以下标都要+1
+				++f[ll][x], q[ll].insert(q[ll].begin() + li, x);
+			}
+		}else{
+			scanf("%d%d%d", &l, &r, &k);
+			l = (l + lastans - 1) % n + 1, r = (r + lastans - 1) % n + 1, k = (k + lastans - 1) % n + 1;
+			if(l > r) swap(l, r);
+			int ll = (l - 1) / sn, rr = (r - 1) / sn, li = (l - 1) % sn, ri = (r - 1) % sn;
+			int ans = 0;
+			if(ll == rr){
+				for(int i = li;i <= ri;i++) ans += q[ll][i] == k;
+			}else{
+				for(int i = ll + 1;i < rr;i++) ans += f[i][k];
+				//printf("%d %d %d %d--\n", ll, rr, li, ri);
+				for(int i = li;i < sn;i++) ans += q[ll][i] == k;
+				for(int i = 0;i <= ri;i++) ans += q[rr][i] == k;
+			}
+			printf("%d\n", lastans = ans);
+		}
+	}
+}</code></hidden>
 =====CF383E=====
-<hidden><code cpp></code></hidden>
+容斥dp+高维前缀和。
+<hidden><code cpp>#include <bits/stdc++.h>
+using namespace std;
+int n;
+int f[1 << 25];
+char s[233];
+int ans;
+int main(){
+	scanf("%d", &n);
+	for(int i = 1;i <= n;i++){
+		scanf("%s", s + 1);
+		int x = 0;
+		for(int j = 1;j <= 3;j++){
+			x |= 1 << (s[j] - 'a');
+		}
+		for(int j = x;j;j = (j - 1) & x){
+			if(__builtin_popcount(j) & 1) f[j]++;
+			else f[j]--;
+		}
+	}
+	for(int i=0;i<24;i++)
+		for(int j=0;j<(1<<24);j++)
+			if(j&(1<<i))f[j]+=f[j^(1<<i)];
+	for(int i=0;i<(1<<24);i++)
+		ans=ans^(f[i]*f[i]);
+	printf("%d", ans);
+}</code></hidden>
 =====CF1045G=====
-<hidden><code cpp></code></hidden>
+思维+二维数点。
+<hidden><code cpp>#include <bits/stdc++.h>
+#define maxn 100086
+using namespace std;
+struct Node{
+	int son[2], val, pri, siz;
+}t[maxn];
+int cnt;
+int root[maxn];
+inline int rand()
+{
+    static int seed=12345;
+    return seed=(int)seed*482711LL%2147483647;
+}
+inline int ls(int x){
+	return t[x].son[0];
+}
+inline int rs(int x){
+	return t[x].son[1];
+}
+void up(int x){
+	t[x].siz = t[ls(x)].siz + t[rs(x)].siz + 1;
+}
+int newnode(int val){
+	cnt++;
+	t[cnt].val = val;
+	t[cnt].pri = rand();
+	t[cnt].siz = 1;
+	return cnt;
+}
+void split(int x, int val, int &a, int &b){//x起始 val权值 a b为两个根编号
+	if(!x){
+		a = b = 0;
+		return;
+	}
+	if(t[x].val <= val) a = x, split(rs(x), val, t[x].son[1], b);
+	else b = x, split(ls(x), val, a, t[x].son[0]);
+	up(x);
+}
+int merge(int x, int y){//返回根编号
+	if(x == 0 || y == 0) return x + y;
+	if(t[x].pri > t[y].pri){
+		t[x].son[1] = merge(rs(x), y);
+		up(x);
+		return x;
+	}else{
+		t[y].son[0] = merge(x, ls(y));
+		up(y);
+		return y;
+	}
+}
+int n, k;
+struct N{
+	int x, r, q;
+}a[maxn];
+inline bool cmp(N x, N y){
+	return x.r > y.r;
+}
+long long ans;
+int b[maxn], n0;
+int A, B, C, D;
+int main(){
+	scanf("%d%d", &n, &k);
+	for(int i = 1;i <= n;i++) scanf("%d%d%d", &a[i].x, &a[i].r, &a[i].q), b[i] = a[i].q;
+	sort(a + 1, a + 1 + n, cmp);
+	sort(b + 1, b + 1 + n);
+	n0 = unique(b + 1, b + 1 + n) - (b + 1);
+	for(int i = 1;i <= n;i++){
+		int x = lower_bound(b + 1, b + 1 + n0, a[i].q) - b;
+		for(int j = x;j <= n0 && b[j] - b[x] <= k;j++){
+			split(root[j], a[i].x - a[i].r - 1, A, B);
+			split(B, a[i].x + a[i].r, C, D);
+			ans += t[C].siz;
+			root[j] = merge(A, merge(C, D));
+		}
+		for(int j = x - 1;j && b[x] - b[j] <= k;j--){
+			split(root[j], a[i].x - a[i].r - 1, A, B);
+			split(B, a[i].x + a[i].r, C, D);
+			ans += t[C].siz;
+			root[j] = merge(A, merge(C, D));
+		}
+		split(root[x], a[i].x, A, B);
+		root[x] = merge(A, merge(newnode(a[i].x), B));
+	}
+	printf("%lld", ans);
+}</code></hidden>
 =====CF797D=====
-<hidden><code cpp></code></hidden>
+思维+二叉搜索树。
+<hidden><code cpp>#include <bits/stdc++.h>
+#define maxn 100086
+using namespace std;
+int n;
+int val[maxn];
+int son[maxn][2];
+bool tag[maxn];
+map<int, bool> mp;
+int ans;
+void dfs(int x, int l, int r){
+	if(val[x] < l && r < val[x]) mp[val[x]] = true;
+	if(son[x][0] != -1) dfs(son[x][0], min(l, val[x]), r);
+	if(son[x][1] != -1) dfs(son[x][1], l, max(r, val[x]));
+}
+int main(){
+	scanf("%d", &n);
+	for(int i = 1;i <= n;i++){
+		scanf("%d%d%d", &val[i], &son[i][0], &son[i][1]);
+		if(son[i][0] != -1) tag[son[i][0]] = true;
+		if(son[i][1] != -1) tag[son[i][1]] = true;
+	}
+	for(int i = 1;i <= n;i++){
+		if(!tag[i]){
+			dfs(i, 1e9 + 1, -1);
+			break;
+		}
+	}
+	for(int i = 1;i <= n;i++) if(!mp[val[i]]) ans++;
+	printf("%d", ans);
+}</code></hidden>
 =====CF979D=====
-<hidden><code cpp></code></hidden>
+Trie+数论。
+<hidden><code cpp>#include <bits/stdc++.h>
+#define maxn 100086
+using namespace std;
+int son[maxn << 8][2], val[maxn << 8];
+int cnt = maxn;
+void insert(int x, int y){
+	for(int i = 1 << 20;i;i >>= 1){
+		bool z = (y & i) != 0;
+		if(!son[x][z]) son[x][z] = ++cnt, val[son[x][z]] = maxn;
+		x = son[x][z], val[x] = min(val[x], y);
+		//printf("%d %d %d--\n", x, i, val[x]);
+	}
+}
+int query(int x, int y, int s){
+	int ans = 0;
+	for(int i = 1 << 20;i;i >>= 1){
+		//printf("%d %d %d %d--\n", x, y, s, i);
+		bool z = (y & i) != 0;
+		if(val[son[x][z ^ 1]] <= s) x = son[x][z ^ 1], ans += (z ^ 1) * i;
+		else if(val[son[x][z]] <= s) x = son[x][z], ans += z * i;
+		else return -1;
+	}
+	return ans;
+}
+int n;
+int opt, x, y, z;
+int main(){
+	scanf("%d", &n);
+	val[0] = maxn;
+	while(n--){
+		scanf("%d", &opt);
+		if(opt == 1){
+			scanf("%d", &x);
+			for(int i = 1;i * i <= x;i++){
+				if(x % i) continue;
+				insert(i, x);
+				if(i * i != x) insert(x / i, x);
+			}
+		}else{
+			scanf("%d%d%d", &x, &y, &z);
+			if(x % y){
+				puts("-1");
+				continue;
+			}
+			printf("%d\n", query(y, x, z - x));
+		}
+	}
+}</code></hidden>
 =====CF1093G=====
-<hidden><code cpp></code></hidden>
+高维曼哈顿距离+线段树。
+<hidden><code cpp>#include <bits/stdc++.h>
+#define maxn 200086
+using namespace std;
+struct Node{
+	int sum[32];
+	Node(){
+		memset(sum, -0x3f, sizeof(sum));
+	}
+	inline int & operator [] (int i){
+		return sum[i];
+	}
+}t[maxn << 2];
+#define ls(x) (x << 1)
+#define rs(x) (x << 1 | 1)
+inline void up(int x){
+	for(int i = 0;i < 32;i++) t[x][i] = max(t[ls(x)][i], t[rs(x)][i]);
+}
+void modify(int x, int l, int r, int pos, Node d){
+	if(l == r){
+		t[x] = d;
+		return;
+	}
+	int mid = l + r >> 1;
+	if(mid >= pos) modify(ls(x), l, mid, pos, d);
+	else modify(rs(x), mid + 1, r, pos, d);
+	up(x);
+}
+Node query(int x, int l, int r, int ll, int rr){
+	if(ll <= l && r <= rr) return t[x];
+	int mid = l + r >> 1;
+	Node a, b;
+	if(mid >= ll){
+		b = query(ls(x), l, mid, ll, rr);
+		for(int i = 0;i < 32;i++) a[i] = max(a[i], b[i]);
+	}
+	if(mid < rr){
+		b = query(rs(x), mid + 1, r, ll, rr);
+		for(int i = 0;i < 32;i++) a[i] = max(a[i], b[i]);
+	}
+	return a;
+}
+int n, k, x, y;
+int q, opt;
+Node a;
+int main(){
+	scanf("%d%d", &n, &k);
+	for(int i = 1;i <= n;i++){
+		memset(a.sum, 0, sizeof(a.sum));
+		for(int j = 0;j < k;j++){
+			scanf("%d", &x);
+			for(int l = 0;l < 32;l++){
+				if(l & (1 << j)) a[l] += x;
+				else a[l] -= x;
+			}
+		}
+		modify(1, 1, n, i, a);
+	}
+	scanf("%d", &q);
+	while(q--){
+		scanf("%d", &opt);
+		if(opt == 1){
+			int i;
+			scanf("%d", &i);
+			memset(a.sum, 0, sizeof(a.sum));
+			for(int j = 0;j < k;j++){
+				scanf("%d", &x);
+				for(int l = 0;l < 32;l++){
+					if(l & (1 << j)) a[l] += x;
+					else a[l] -= x;
+				}
+			}
+			modify(1, 1, n, i, a);
+		}else{
+			scanf("%d%d", &x, &y);
+			a = query(1, 1, n, x, y);
+			int ans = -1e9;
+			for(int i = 0;i < (1 << k);i++) ans = max(ans, a[i] + a[(1 << k) - 1 - i]);
+			printf("%d\n", ans);
+		}
+	}
+}</code></hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具