首页 > 其他分享 >CF1580C Train Maintenance题解

CF1580C Train Maintenance题解

时间:2023-05-14 14:37:37浏览次数:42  
标签:opt int 题解 sqrt leq Train Maintenance include day

我们以 \(\sqrt m\) 为分界点来进行平衡。

设当前在进行第 \(k\) 次操作,询问 \(i\)。

对于 \(x_i + y_i \leq \sqrt m\),可以在 \(last_{x_i + y_i,day \bmod (x_i + y_i)}\) 上 \(+1\),其中 \(day\) 表示维修的时间,\(k + x_i \leq day \leq k + x_i + y_i - 1\),输出时暴力统计即可。

对于 \(x_i + y_i > \sqrt m\) 的,可以在利用差分数组在 \(f_{day_1}\) 上 \(+ 1\),在 \(f_{day_2}\) 上 \(-1\),其中 \(day_1\) 表示所有的维修时间的开始时间,\(day_2\) 表示所有维修时间的结束时间的后面一天。

时间复杂度:\(O(m\sqrt m)\)。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 200010, V = 450;

int n, m, s;
int st[N];
int f[N];
int last[V][V];
int x[N], y[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	s = sqrt(m);
	for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
	int opt, a;
	int sum = 0;
	for (int i = 1; i <= m; i++) {
		cin >> opt >> a;
		if (opt == 1) {
			if (x[a] + y[a] > s) {
				for (int j = i + x[a]; j <= m; j += x[a] + y[a]) {
					f[j] += 1;
					if (j + y[a] <= m) f[j + y[a]] -= 1;
				}
			}
			else {
				int b = i + x[a], e = i + x[a] + y[a] - 1;
				for (int j = b; j <= e; j++) {
					last[x[a] + y[a]][j % (x[a] + y[a])]++;
				}
			}
			st[a] = i;
		}
		else {
			if (x[a] + y[a] > s) {
				for (int j = st[a] + x[a]; j <= m; j += x[a] + y[a]) {
					f[j] -= 1;
					if (j < i) sum--;
					if (j + y[a] <= m) {
					    f[j + y[a]] += 1;
					    if (j + y[a] < i) sum++;
					}
				}
			}
			else {
				for (int j = st[a] + x[a]; j < st[a] + x[a] + y[a]; j++) {
					last[x[a] + y[a]][j % (x[a] + y[a])]--;
				}
			}
		}
		sum += f[i];
		int res = sum;
		for (int j = 1; j <= s; j++) res += last[j][i % j];
		cout << res << '\n';
	}
	return 0;
}

标签:opt,int,题解,sqrt,leq,Train,Maintenance,include,day
From: https://www.cnblogs.com/PlayWithCPP/p/17399250.html

相关文章

  • CF961E Tufurama题解
    我们维护一个存储下标数据的树状数组,先将\(1\simn\)插入树状数组。用\(a\)表示原数组,\(b\)表示按照\(a_i\)排序后的数组。我们从\(1\)开始统计,直到\(n\),统计时:将\(i\)删除,不能把自己算进去。为了排除\(a_j<i\)的部分,可以从前往后扫描\(b\),一直删,......
  • CF1794B Not Dividing题解
    如果\(a_i\)可以整除\(a_{i-1}\),只要在\(a_i\)上\(+1\)即可,这样\(a_i\bmoda_{i-1}=1\)就满足题目要求了,如果这样算来最多进行\(n\)次操作。但同时要注意\(a_{i-1}=1\)的情况。如果\(a_{i-1}\)为\(1\),那么怎么\(+1\)都是\(a_i\bmoda_{i-1}=......
  • CF1794C Scoring Subsequences题解
    文中\(a\)为题目中给的\(a\)。如果我们要求\(a_1,a_2,a_3,\dots,a_m\)的结果,那么我们可以把\(a\)数组从后往前依次除以\(i\),\(i\)从\(1\)到\(n\),即为\(\frac{a_1}{m},\frac{a_2}{m-1},\frac{a_3}{m-2},\dots,\frac{a_{m-1}}{2},\frac{a_m}{1}\),并将其保......
  • CF371D题解
    思路:定义一个权值并查集,权值保存这个集合还可以存下多少水。如果这个集合可以存放的水已经小于要装入的水,就将这个集合与下一个集合合并。否则,直接把这个集合可以存放的水减去要装入的水的体积。代码:#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;......
  • CF1799B Equalize by Divide题解
    本蒟蒻学习了jiangly大佬的思想,来发一个题解。大致题意:给定一个\(n\)个元素的数组\(a\),每次可以选择\(a[i]\)和\(a[j]\),然后使\(a[i]=\lceil\frac{a_i}{a_j}\rceil\),如果最后可以使数组中的所有元素都相等,那么输出Yes,并输出每一个操作\(i,j\);否则输出No。本人不......
  • CF1728A Colored Balls: Revisited题解
    去我的Blog观看修改时间:2022/9/11修改了格式与标点修改时间:2022/9/13修改了个别不严谨的语句题目大意有\(n\)种颜色的球,颜色为\(i\)的球为\(cnt_i\)个(\(cnt_1+cnt_2+\dots+cnt_n\)为奇数)。每次从球堆中取出\(2\)个颜色不相同的球,问最后可能剩下哪种颜色的球(输出任意......
  • 常见问题解决 --- python必备技能 换源
    源是什么源是编程开发或则是操作系统要使用的第三方依赖软件应用市场,源又从何而来,其实源来自其他的源的克隆,或者是源提供者自己收集,编译,又或者作者的上传为什么要换源这些源往往都在国外,国内以为你懂的原因无法直接访问或者特别慢怎么换Windows下python永久换源方式有两种:修......
  • 常见问题解决 --- pip报错【WARNING: Retrying (Retry(total=4, connect=None, read=N
    问题现象【WARNING:Retrying(Retry(total=4,connect=None,read=None,redirect=None,st】解决方法:出现该错误信息是因为pip源连接证书验证失败,增加参数 --trusted-host例如pipinstallmatplotlib-ihttp://mirrors.aliyun.com/pypi/simple--trusted-hostmirrors.al......
  • 【题解】ars[A001]相控阵
    Link→模拟赛T1一道简单好想小可爱题。首先我们很容易得到一个结论,就是若想使总作用力最大,那么五个核弹中一定会有四个反应关系去对总作用力产生贡献。证明的话:五个核弹相当于一个五元环,不同模式相当于对点进行染色,我们不妨规定两种模式分别染色为红和蓝。因为边数\(n\)......
  • P8430 题解
    前言题目传送门!更好的阅读体验?比较妙的交互题。思路题意就是每次可以询问\([l,r]\)的括号子序列是否为合法,\((n-1)\)次询问后,需要求出整个括号序列。括号序列,自然想到栈。考虑每次进行一个\([\text{top},i]\)的询问。如果是合法,那么\(a_{\text{top}}=\text{LEFT},a......