6.20训练日记

6.21的评论,6.20在搞学校工作,唉,训练还是得抓紧的

G. Count the Trains链接

思考了很久,但还是想不到怎么维护一些数据来达到每次更新的时候怎么快速求答案.一直在思考修改 i i i的位置,对原数组 a i − 1 , a i + 1 a_{i-1},a_{i+1} ai−1​,ai+1​和根据题目定义的数组 b i + 1 b_{i+1} bi+1​的影响,可以发现,修改 i i i并不会影响 i i i位置之前的答案贡献,但对 b i + 1 b_{i+1} bi+1​后面有影响.如果 b i + 1 b_{i+1} bi+1​的值没有变化,那答案只会在 a i − 1 a_{i-1} ai−1​那里有贡献,如果有变化,那么肯定是变得更小,那么就会使得后边的一些元素 b j > b i + 1 b_j>b_{i+1} bj​>bi+1​通通变成 b i + 1 b_{i+1} bi+1​。这部分答案的贡献就是这些 b j b_j bj​的数目。 那么问题来了,咋快速求呢,不会。 搬运标程了:用 b 数 组 代 表 映 射 完 毕 后 的 a 数 组 b数组代表映射完毕后的a数组 b数组代表映射完毕后的a数组开一个set，保存那些连续段的起始坐标,也就是保存坐标 i i i,如果有 b i < b i − 1 b_ia_{mx},mx是集合S里面的最大值,代表上一个答案的下标 aj​>amx​,mx是集合S里面的最大值,代表上一个答案的下标,那么就会形成一个新的断点,需要我们把 j j j插入里面去. 当修改 a i a_i ai​的时候,需要把所有 j > i 且 a j > a i j>i且a_j>a_i j>i且aj​>ai​的 j j j从集合中全部删去. 在集合S里面, 下 标 j 越 大 , 原 数 组 对 应 的 a j 也 就 越 小 下标j越大,原数组对应的a_j也就越小 下标j越大,原数组对应的aj​也就越小.然后修改后的 a j 与 下 标 j a_j与下标j aj​与下标j考虑是否能插入回原数组, 条件1: j j j下标原本就在这个集合里面了. 条件2: j j j下标不在,但修改后的 a j a_j aj​比集合的前一个元素要小, 满足这两个条件之一就可以了.所以可以直接二分找到自己,比较二分指针前一个的值就能判断当前的值是否需要插入. 对于删除的操作,就是删掉所有 k > j 且 a k > a j k>j且a_k>a_j k>j且ak​>aj​。 代码技巧:用rbegin代表迭代器最后一个元素,用prev(it)函数,找迭代器it的上一个.

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;cin>>T;
	while(T--){
		int n,m;cin>>n>>m;
		vector a(n+1,0);
		for(int i=1;i>a[i];
		set S;
		for(int i=1;ia[i]){
				S.insert(i);
			}
		}
		while(m--){
			int j,d;cin>>j>>d;
			a[j]-=d;
			auto it = S.upper_bound(j);
			if(it!=S.begin()){
				it = prev(it);
				if(*it==j||a[*it]>a[j]) S.insert(j); 
			}
			else S.insert(j);
			while(true){
				it = S.upper_bound(j);
				if(it!=S.end()&&a[*it]>=a[j]) S.erase(it);
				else {
					break;
				} 
			}
			cout