首页 > 其他分享 >CodeForces 1609G A Stroll Around the Matrix

CodeForces 1609G A Stroll Around the Matrix

时间:2024-01-22 15:04:18浏览次数:35  
标签:typedef Around ll CodeForces long maxn define Matrix

洛谷传送门

CF 传送门

我独立做出一道 *3000?

考虑对于单次询问,除了 \(O(nm)\) 的 dp,有没有什么方法能快速算出答案。发现若 \(a_{i + 1} - a_i < b_{j + 1} - b_j\) 则 \(i \gets i + 1\),否则 \(j \gets j + 1\) 是最优的。这个贪心的证明不难,考虑当前新走到某一行或某一列的贡献是差分数组乘上剩下的格子个数,显然选较小的乘上去最优。

那么现在单次询问我们能做到 \(O(n + m)\) 了。观察到 \(n \le 100\),考虑从这里入手。可以枚举每一行,二分出在这一行能走到的最右的列(也就是最大的 \(j\) 使得 \(b_{j + 1} - b_j < a_{i + 1} - a_i\))。用一棵树状数组维护 \(b\) 的二阶差分即可树状数组上二分找到这个位置。

\(a\) 对答案的贡献每次枚举 \(i\) 直接计算即可,\(b\) 对答案的贡献不难发现是 \([1, m]\) 的和加上一些单点的形式(单点的贡献是向下走产生的)。查 \(b\) 的单点的值,考虑转化成 \(b\) 的一阶差分的前缀和,也可以用树状数组维护。

总时间复杂度为 \(O((nm + q) \log m + nq)\)。

code
// Problem: G. A Stroll Around the Matrix
// Contest: Codeforces - Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)
// URL: https://codeforces.com/problemset/problem/1609/G
// Memory Limit: 256 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_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;

const int maxn = 100100;

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

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

struct {
	ll c[maxn];
	
	inline void update(ll x, ll d) {
		for (int i = x; i <= m; i += (i & (-i))) {
			c[i] += d;
		}
	}
	
	inline ll query(int x) {
		ll res = 0;
		for (int i = x; i; i -= (i & (-i))) {
			res += c[i];
		}
		return res;
	}
	
	inline ll find(ll x) {
		ll s = 0, p = 0;
		for (int i = 17; ~i; --i) {
			if (p + (1 << i) < m && s + c[p + (1 << i)] < x) {
				p += (1 << i);
				s += c[p];
			}
		}
		return p;
	}
} t1;

struct {
	ll a[maxn], b[maxn];
	
	inline void update(int x, ll y) {
		for (int i = x; i <= m; i += (i & (-i))) {
			a[i] += y;
			b[i] += x * y;
		}
	}
	
	inline void update(int l, int r, ll x) {
		update(l, x);
		update(r + 1, -x);
	}
	
	inline ll query(int x) {
		ll res = 0;
		for (int i = x; i; i -= (i & (-i))) {
			res += a[i] * (x + 1) - b[i];
		}
		return res;
	}
} t2;

inline ll query(int x) {
	// printf("x: %d %lld\n", x, t2.query(x - 1) + b[1]);
	return t2.query(x - 1) + b[1];
}

inline ll work() {
	ll j = 1, ans = a[n];
	for (int i = 1; i < n; ++i) {
		ll p = max(j - 1, t1.find(a[i + 1] - a[i]));
		ans += a[i] * (p - j + 1);
		j = p + 1;
		ans += a[i] + query(j);
		// printf("%d %lld %lld\n", i, j, ans);
	}
	ans += a[n] * (m - j) + sb;
	return ans;
}

void solve() {
	scanf("%lld%lld%lld", &n, &m, &q);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	for (int i = 1; i <= m; ++i) {
		scanf("%lld", &b[i]);
		sb += b[i];
	}
	for (int i = 1; i < m; ++i) {
		d[i] = b[i + 1] - b[i];
		t1.update(i, d[i] - d[i - 1]);
		t2.update(i, i, d[i]);
	}
	while (q--) {
		ll op, x, y;
		scanf("%lld%lld%lld", &op, &x, &y);
		if (op == 1) {
			for (int i = n - x + 1; i <= n; ++i) {
				a[i] += (i - n + x) * y;
			}
		} else {
			sb += x * (x + 1) / 2 * y;
			x = m - x + 1;
			if (x == 1) {
				b[1] += y;
				x = 2;
			}
			t1.update(x - 1, y);
			t2.update(x - 1, m, y);
		}
		// printf("sb: %lld\n", sb);
		printf("%lld\n", work());
	}
}

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

标签:typedef,Around,ll,CodeForces,long,maxn,define,Matrix
From: https://www.cnblogs.com/zltzlt-blog/p/17980040

相关文章

  • CodeForces 1609F Interesting Sections
    洛谷传送门CF传送门看到\(\max,\min\)考虑单调栈。枚举右端点,计算有多少个符合条件的左端点。单调栈维护的是对于每个右端点,以每个点为左端点的后缀\(\max,\min\)形成的极长的段。先枚举\(\text{popcount}=k\),然后如果一个段的\(\max\)的\(\text{popcount}=k\)......
  • (区间覆盖问题)P5019 [NOIP2018 提高组] 铺设道路和Educational Codeforces Round 158 (
    区间覆盖问题这里EducationalCodeforcesRound158(RatedforDiv.2)b题和[NOIP2018提高组]铺设道路两道典型题目,本质是相同的。这里由于题目多次出现,特此记录。解题思路:首先我们得对区间做划分,那么划分思路可以是从小到大也可以是从大到小的异常点来做划分(我这是由大到......
  • hey_left 12 Codeforces Round 859 (Div. 4) 续
    F.模拟题,不难只是比较繁琐,需要分情况讨论debug:如何判断永远走不到终点格?原思路是这个点同时这个点指向的方向被经过了,那么就是走的重复的路,走不到终点但不知为何map出了一些问题后来看题解,只要步数很大了还走不到那么就永远走不到于是我把map删了,过了#include<bits/stdc......
  • hey_left 11 Codeforces Round 859 (Div. 4)
    题目链接A.直接判断输出#include<bits/stdc++.h>usingnamespacestd;voidsolve(){inta,b,c;cin>>a>>b>>c;if(a+b==c)cout<<'+'<<'\n';elseif(a-b==c)cout<<"-"<<'\n&#......
  • CodeForces 342E Xenia and Tree
    洛谷传送门CF传送门比较谔谔,为什么题解区都在群魔乱舞。不是有个很简单的点分树做法吗。考虑建出点分树,由点分树的性质可得任意两点在点分树上的LCA一定在它们的路径上。然后每次暴力跳父亲,每个分治中心维护一个\(f_i\)表示距离\(i\)最近的红色点的距离即可。若使用df......
  • 比赛必备——codeforces better 和 atcoder better 的安装教程
    大家有没有像我一样英语不太好然后又想要打cf和atc的呢?(可能全世界就我英语不好)这里有两个强力的工具可以帮助我们解决这一问题——codeforcesbetter和atcoderbetter。由于我只用的是edge,所以下面默认为edge浏览器篡改猴首先我们需要安装篡改猴,link。codeforcesbe......
  • hey_left 10 Codeforces Round 871 (Div. 4) 再续
    题目链接H.没思路,查看题解选择数组的非连续的子序列,就是每个数选或不选的问题求个数,易dp求子序列的数二进制相与结果有k个1的个数把所有结果记录,再去筛选满足条件的结果f[i][j]表示到第i个数,相与结果为j的子序列个数正向思维:多个数相与得到结果dp思维:枚举结果,考虑数如何......
  • hey_left 9 Codeforces Round 871 (Div. 4) 续
    题目链接E.连通块的搜索debug:用不上回溯,把连通块的贡献全部加起来#include<bits/stdc++.h>usingnamespacestd;intn,m;intg[1010][1010];boolvis[1010][1010];intma,tmp;intdx[5]={-1,1,0,0};intdy[5]={0,0,1,-1};voiddfs(intx,inty){tmp+=g[x][y];......
  • Educational Codeforces Round 161 (Rated for Div. 2)
    基本情况A犯病卡半小时。主要就是太着急,题目没有彻底分析清楚就开始想一些错误做法。C最优想法出来的慢。E比较好想。C.ClosestCitiesProblem-C-Codeforces就,显然是能走最近城市就走,不行就不走。一开始弄了一个自作聪明的预处理,但实际上每次查询还是\(\operatorn......
  • Codeforces Round 920 (Div. 3)
    题目链接点这里这场div3F题的算法很基础,但是我此前居然完全没接触过。(芙莉莲震惊.jpg)不过这下能够算法沙漠面积--了。CF1921ASquarevoidsolve(){intx1=1e9,y1=1e9,x2=-1e9,y2=-1e9,x,y;for(inti=1;i<=4;++i){cin>>x......