首页 > 其他分享 >CodeForces 1928F Digital Patterns

CodeForces 1928F Digital Patterns

时间：2024-02-13 19:25:08浏览次数：38  
标签：insert updy updx int sum CodeForces Patterns Digital prev

洛谷传送门

CF 传送门

为什么我场上被卡常了。

转化题意，将 \(a, b\) 差分，答案为在 \(a, b\) 选出相同长度的不含 \(0\) 的子段方案数。

设 \(a\) 选出长度为 \(i\) 的不含 \(0\) 的子段方案数为 \(x_i\)，\(b\) 选出长度为 \(i\) 的不含 \(0\) 的子段方案数为 \(y_i\)。答案为 \(\sum x_i y_i\)。考虑线段树维护这个东西。

一个 \(a\) 中长度为 \(l\) 的极长子段会给 \(\forall k \in [1, l]\) 的 \(x_k\) 贡献 \(k - l + 1\)。\(b\) 同理。\(k + 1\) 和 \(-l\) 是独立的，先考虑 \(-l\) 这部分。也就是要支持 \(x_i \gets x_i + di\) 或 \(y_i \gets y_i + di\)。

只考虑修改 \(x\)，\(y\) 是对称的。拆式子：\(\sum (x_i + di) y_i = \sum x_i y_i + d \sum i y_i\)。再维护 \(\sum i x_i\) 和 \(\sum i y_i\) 就可以完成 \(\sum x_i y_i\) 的修改。\(\sum i x_i\) 的修改是容易的，考虑 \(\sum i (x_i + i) = \sum i x_i + \sum i^2\)，后者显然可以 \(O(1)\) 求的。

还要支持 \(x_i \gets x_i + d\) 或者 \(y_i \gets y_i + d\)。继续拆式子：\(\sum (x_i + d) y_i = \sum x_i y_i + d \sum x_i\)。再维护 \(\sum x_i, \sum y_i\) 即可。

于是线段树每个结点维护 \(5\) 个值：\(\sum x_i y_i, \sum x_i, \sum y_i, \sum i x_i, \sum i y_i\) 和 \(4\) 种懒标记即可。

差分后区间加变成了单点修改。考虑对 \(a, b\) 分别开个 set 维护非 \(0\) 极长连续段。显然单点修改只会加入或删除 \(O(1)\) 个段，讨论下就行了。

时间复杂度 \(O((n + q) \log n)\)，但是线段树的常数巨大，实现精细点就能过了。

真的有人会想看 7KB+ 的代码吗？ 
// Problem: F. Digital Patterns
// Contest: Codeforces - Codeforces Round 924 (Div. 2)
// URL: https://codeforces.com/contest/1928/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb insert_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar();
    int x = 0;
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return f ? -x : x;
}

const int maxn = 300100;

ll n, m, q, a[maxn], b[maxn];

struct node {
	ll sxy, sx, sy, six, siy;
};

inline node operator + (const node &a, const node &b) {
	node res;
	res.sxy = a.sxy + b.sxy;
	res.sx = a.sx + b.sx;
	res.sy = a.sy + b.sy;
	res.six = a.six + b.six;
	res.siy = a.siy + b.siy;
	return res;
}

inline ll calc1(ll l, ll r) {
	return (l + r) * (r - l + 1) / 2;
}

inline ll calc2(ll n) {
	return n * (n + 1) * (n * 2 + 1) / 6;
}

inline ll calc2(ll l, ll r) {
	return calc2(r) - calc2(l - 1);
}

namespace SGT {
	node a[maxn << 2];
	ll ta1[maxn << 2], ta2[maxn << 2], tb1[maxn << 2], tb2[maxn << 2];
	
	inline void pushup(int x) {
		a[x] = a[x << 1] + a[x << 1 | 1];
	}
	
	inline void pushta1(int x, int l, int r, ll y) {
		node &u = a[x];
		u.sxy += y * u.siy;
		u.sx += y * calc1(l, r);
		u.six += y * calc2(l, r);
		ta1[x] += y;
	}
	
	inline void pushta2(int x, int l, int r, ll y) {
		node &u = a[x];
		u.sxy += y * u.sy;
		u.sx += y * (r - l + 1);
		u.six += y * calc1(l, r);
		ta2[x] += y;
	}
	
	inline void pushtb1(int x, int l, int r, ll y) {
		node &u = a[x];
		u.sxy += y * u.six;
		u.sy += y * calc1(l, r);
		u.siy += y * calc2(l, r);
		tb1[x] += y;
	}
	
	inline void pushtb2(int x, int l, int r, ll y) {
		node &u = a[x];
		u.sxy += y * u.sx;
		u.sy += y * (r - l + 1);
		u.siy += y * calc1(l, r);
		tb2[x] += y;
	}
	
	inline void pushdown(int x, int l, int r) {
		int mid = (l + r) >> 1;
		if (ta1[x]) {
			pushta1(x << 1, l, mid, ta1[x]);
			pushta1(x << 1 | 1, mid + 1, r, ta1[x]);
			ta1[x] = 0;
		}
		if (ta2[x]) {
			pushta2(x << 1, l, mid, ta2[x]);
			pushta2(x << 1 | 1, mid + 1, r, ta2[x]);
			ta2[x] = 0;
		}
		if (tb1[x]) {
			pushtb1(x << 1, l, mid, tb1[x]);
			pushtb1(x << 1 | 1, mid + 1, r, tb1[x]);
			tb1[x] = 0;
		}
		if (tb2[x]) {
			pushtb2(x << 1, l, mid, tb2[x]);
			pushtb2(x << 1 | 1, mid + 1, r, tb2[x]);
			tb2[x] = 0;
		}
	}
	
	void upda1(int rt, int l, int r, int ql, int qr, ll x) {
		if (ql <= l && r <= qr) {
			pushta1(rt, l, r, x);
			return;
		}
		pushdown(rt, l, r);
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			upda1(rt << 1, l, mid, ql, qr, x);
		}
		if (qr > mid) {
			upda1(rt << 1 | 1, mid + 1, r, ql, qr, x);
		}
		pushup(rt);
	}
	
	void upda2(int rt, int l, int r, int ql, int qr, ll x) {
		if (ql <= l && r <= qr) {
			pushta2(rt, l, r, x);
			return;
		}
		pushdown(rt, l, r);
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			upda2(rt << 1, l, mid, ql, qr, x);
		}
		if (qr > mid) {
			upda2(rt << 1 | 1, mid + 1, r, ql, qr, x);
		}
		pushup(rt);
	}
	
	void updb1(int rt, int l, int r, int ql, int qr, ll x) {
		if (ql <= l && r <= qr) {
			pushtb1(rt, l, r, x);
			return;
		}
		pushdown(rt, l, r);
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			updb1(rt << 1, l, mid, ql, qr, x);
		}
		if (qr > mid) {
			updb1(rt << 1 | 1, mid + 1, r, ql, qr, x);
		}
		pushup(rt);
	}
	
	void updb2(int rt, int l, int r, int ql, int qr, ll x) {
		if (ql <= l && r <= qr) {
			pushtb2(rt, l, r, x);
			return;
		}
		pushdown(rt, l, r);
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			updb2(rt << 1, l, mid, ql, qr, x);
		}
		if (qr > mid) {
			updb2(rt << 1 | 1, mid + 1, r, ql, qr, x);
		}
		pushup(rt);
	}
}

inline void updx(int x, int y) {
	SGT::upda1(1, 1, n, 1, x, -y);
	SGT::upda2(1, 1, n, 1, x, y * (x + 1));
}

inline void updy(int x, int y) {
	SGT::updb1(1, 1, n, 1, x, -y);
	SGT::updb2(1, 1, n, 1, x, y * (x + 1));
}

set<int> S, T;
int f[maxn], g[maxn];

inline void addx(int x) {
	auto i = S.lower_bound(x);
	if (i != S.end() && *i == x + 1) {
		updx(f[*i] - *i + 1, -1);
		int l = x, r = f[*i];
		if (i != S.begin() && f[*prev(i)] == x - 1) {
			int p = *prev(i);
			l = p;
			updx(f[p] - p + 1, -1);
			S.erase(prev(i));
		}
		S.erase(i);
		S.insert(l);
		f[l] = r;
		updx(r - l + 1, 1);
	} else if (i != S.begin() && f[*prev(i)] == x - 1) {
		int p = *prev(i);
		S.erase(prev(i));
		int l = p, r = x;
		updx(f[p] - p + 1, -1);
		f[l] = r;
		S.insert(l);
		updx(r - l + 1, 1);
	} else {
		updx(1, 1);
		S.insert(x);
		f[x] = x;
	}
}

inline void delx(int x) {
	auto i = --S.upper_bound(x);
	int p = *i;
	int q = f[p];
	S.erase(i);
	updx(q - p + 1, -1);
	if (p < x) {
		updx(x - p, 1);
		S.insert(p);
		f[p] = x - 1;
	}
	if (x < q) {
		updx(q - x, 1);
		S.insert(x + 1);
		f[x + 1] = q;
	}
}

inline void addy(int x) {
	auto i = T.lower_bound(x);
	if (i != T.end() && *i == x + 1) {
		updy(g[*i] - *i + 1, -1);
		int l = x, r = g[*i];
		if (i != T.begin() && g[*prev(i)] == x - 1) {
			int p = *prev(i);
			l = p;
			updy(g[p] - p + 1, -1);
			T.erase(prev(i));
		}
		T.erase(i);
		T.insert(l);
		g[l] = r;
		updy(r - l + 1, 1);
	} else if (i != T.begin() && g[*prev(i)] == x - 1) {
		int p = *prev(i);
		T.erase(prev(i));
		int l = p, r = x;
		updy(g[p] - p + 1, -1);
		g[l] = r;
		T.insert(l);
		updy(r - l + 1, 1);
	} else {
		updy(1, 1);
		T.insert(x);
		g[x] = x;
	}
}

inline void dely(int x) {
	auto i = --T.upper_bound(x);
	int p = *i;
	int q = g[p];
	T.erase(i);
	updy(q - p + 1, -1);
	if (p < x) {
		updy(x - p, 1);
		T.insert(p);
		g[p] = x - 1;
	}
	if (x < q) {
		updy(q - x, 1);
		T.insert(x + 1);
		g[x + 1] = q;
	}
}

void solve() {
	n = read();
	m = read();
	q = read();
	for (int i = 1; i <= n; ++i) {
		a[i] = read();
	}
	for (int i = 1; i <= m; ++i) {
		b[i] = read();
	}
	for (int i = 1; i < n; ++i) {
		a[i] -= a[i + 1];
	}
	for (int i = 1; i < m; ++i) {
		b[i] -= b[i + 1];
	}
	ll nn = max(n, m) - 1, tn = n, tm = m;
	n = nn;
	for (int i = 1, j = 1; i < tn; i = (++j)) {
		if (!a[i]) {
			continue;
		}
		while (j + 1 < tn && a[j + 1]) {
			++j;
		}
		S.insert(i);
		f[i] = j;
		updx(j - i + 1, 1);
	}
	for (int i = 1, j = 1; i < tm; i = (++j)) {
		if (!b[i]) {
			continue;
		}
		while (j + 1 < tm && b[j + 1]) {
			++j;
		}
		T.insert(i);
		g[i] = j;
		updy(j - i + 1, 1);
	}
	printf("%lld\n", tn * tm + SGT::a[1].sxy);
	while (q--) {
		ll op, l, r, x;
		op = read();
		l = read();
		r = read();
		x = read();
		--l;
		if (op == 1) {
			if (l) {
				ll p = a[l];
				a[l] -= x;
				if (!p && a[l]) {
					addx(l);
				} else if (p && !a[l]) {
					delx(l);
				}
			}
			if (r < tn) {
				ll p = a[r];
				a[r] += x;
				if (!p && a[r]) {
					addx(r);
				} else if (p && !a[r]) {
					delx(r);
				}
			}
		} else {
			if (l) {
				ll p = b[l];
				b[l] -= x;
				if (!p && b[l]) {
					addy(l);
				} else if (p && !b[l]) {
					dely(l);
				}
			}
			if (r < tm) {
				ll p = b[r];
				b[r] += x;
				if (!p && b[r]) {
					addy(r);
				} else if (p && !b[r]) {
					dely(r);
				}
			}
		}
		printf("%lld\n", tn * tm + SGT::a[1].sxy);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签：insert,updy,updx,int,sum,CodeForces,Patterns,Digital,prev
From： https://www.cnblogs.com/zltzlt-blog/p/18014746

相关文章

  • Codeforces Round 729 (Div. 2)B. Plus and Multiply（构造、数学）
    题面链接B.PlusandMultiply题意给定\(n，a，b\)可以进行的操作\(*a\)\(+b\)最开始的数是1问能否经过上面的两种操作将1变为n题解这题的关键是能不能想出来这个集合里面的数的统一的表达形式所有数都可以表示为\(a^x+y*b\)然后只要存在\(x\)和\(y\)，使得\(a^x+y*......
  • Codeforces Round 922 (Div. 2) A~C
    A.BrickWall#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn,m;cin>>n>>m;intans=n*(m/2);cout<<ans<<"\n";}intmain(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int......
  • Codeforces Round 923 (Div. 3)
    A.MakeitWhite#include<bits/stdc++.h>usingnamespacestd;voidsolve(){ inta,b,n; strings; cin>>n>>s; for(inti=0;i<n;i++){ if(s[i]=='B'){ a=i; break; } } for(inti=n-1;i>=0;i--){ if(s[i]=='B&......
  • Codeforces Round 924 (Div. 2)
    B.Equalize与数组的原始顺序无关，直接排序，然后用双指针滑动范围a[r]-a[l]小于n#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;voidsolve(){ intn; cin>>n; set<int>st; for(inti=1;i<=n;i++){ intx; cin>>x; st.insert(x); } ......
  • Codeforces Round 924 (Div. 2)
    1928D-LonelyMountainDungeons题意：有\(n\)个种族，第\(i\)个种族\(c_i\)个生物，现在要将这些生物分成若干组，每一对不在同一组但是同一种族的生物会对这种分组的价值贡献\(b\)，如果分了\(k\)组，则价值要减去\((k-1)x\)，求最大价值。\(n\le10^5，\sumc_i\le10^5\)思......
  • Codeforces Round 303 (Div. 2)C. Kefa and Park（DFS、实现）
    @目录题面链接题意题解代码总结题面链接C.KefaandPark题意求叶节点数量，叶节点满足，从根节点到叶节点的路径上最长连续1的长度小于m题解这道题目主要是实现，当不满足条件时直接返回。到达叶节点后统计答案，用vector存图的话，无向图时，叶节点的边只有一条，也就是\(g[i].size()......
  • Codeforces Round 924 (Div. 2)B. Equalize（思维+双指针）
    目录题面链接题意题解代码题面链接B.Equalize题意给一个数组\(a\)，然后让你给这个数组加上一个排列，求出现最多的次数题解赛时没过不应该。最开始很容易想到要去重，因为重复的元素对于答案是没有贡献的。去重后排序。，然后维护一个极差小于n-1的区间，，区间长度就是可能的答案......
  • Codeforces Round 924 (Div. 2)
    E-ModularSequence题意给定\(n,x,y,s\)，求是否有长为\(n\)的一个数列\(\{a\}\)满足\(a_1=x\)且\(\foralli>1:a_i=a_{i-1}+y\lora_i=a_{i-1}\bmody\)且\(\sum\limits_{i=1}^{n}a_i=s\)。\(\sumn,\sums\le2\times10......
  • Codeforces Round 924 (Div. 2)
    不会F的场。ACode#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;intmain(){ ios::sync_with_stdio(false); cin.tie(0); intt; cin>>t; while(t--){ inta,b; cin>>a>>b; intf=0; if(a%2==0&&am......
  • Codeforces Round 924 (Div. 2)
    CodeforcesRound924(Div.2)A-RectangleCutting解题思路:初始矩形长宽为\((a,b)\)，如果我们切\(a\),那么一定不能再拼接\(a\)，否则一定一样。所以我们拼接\(b\)，即将\(a\)对半分开得到两个\((\frac{a}{2},b)\)矩形拼接。此时，如果\(\frac{a}{2}=b\)那么拼接出来的矩形和初......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99