首页 > 代码库 > CF444C DZY Loves Colors

CF444C DZY Loves Colors

2024-07-11 05:45:03   217人阅读

考试完之后打的第一场CF，异常惨烈呀，又只做出了一题了。A题呆滞的看了很久，领悟到了出题者的暗示，应该就是两个点的时候最大吧，不然的话这题肯定特别难敲，YY一发交上去然后就过了。然后就在不停地YY B题，赛后听了英姐的答案，看了题解，发现其实自己是捕捉到了正确的解题思路的，但是因为不知道怎么算出期望的复杂度，因而就没敢敲，哪里会想到算复杂度会算期望的情况的呢－ －0

然后就来说下坑爹的C题了，比赛的时候看了觉得是线段树，它支持段更，但是每次段更的时候对于每个点，更新的差值|x-y|要被记录下来，心里想，要是用线段树必然会TLE的，赛后看了题解也觉得这不是O(n^2)的节奏吗。。。后来学习了才明白，单次操作确实有可能会是O(n)的，但是均摊下来是可以O(1)的。

单次复杂度之所以会达到O(n)是因为下面的clear函数，如果clear的那个区间本身没有连成一片（即cov==-1）,那么必然要将这个区间左右递归一次，直到往下递归的区间里有连成一片的才会停止，于是乎当我clear某个区间的时候的复杂度取决于该区间下有多少个不连续的区间。一开始所有区间都是不连续的（1，2，3，4...n），假如我一开始更新1~n,那么复杂度就是O(n)的，因为1~n下面的区间有n个不连续的区间，但是这次操作之后不连续的区间就变成1了。然后不难发现的是，每次更新一段的时候，最多会产生2个不连续的区间，所以m次操作后，不连续的总区间数控制在n+2m（局部最大是n个，就像一开始一样），所以所有clear的复杂度加起来撑死了也在n+2m这个范围内。因此复杂度是不会达到O(n^2)的。 智硬下想了好久才领悟到了为什么复杂度能控制在O(nlogn)下。

#pragma warning(disable:4996)#include <cstdio>#include <algorithm>#include <iostream>#include <cstring>#include <string>#include <vector>#include <cmath>using namespace std;#define ll long long#define maxn 100500struct Node{	int l, r;	ll sum;	ll delta;	ll cov;}N[4*maxn];int n, m;void build(int i, int L, int R){	N[i].l = L; N[i].r = R; N[i].sum = N[i].delta = 0; N[i].cov = -1;	if (L >= R){		N[i].cov = L;		return;	}	int M = (L + R) >> 1;	build(i << 1, L, M);	build(i << 1 | 1, M + 1, R);}void clear(int i, int L, int R, int val){	if (N[i].cov != -1){		N[i].delta += abs(val - N[i].cov);		N[i].sum += abs(val - N[i].cov)*(N[i].r - N[i].l + 1);	}	else{		clear(i << 1, L, R, val);		clear(i << 1 | 1, L, R, val);		N[i].sum = N[i << 1].sum + N[i << 1 | 1].sum + 1LL * N[i].delta*(N[i].r - N[i].l + 1);	}	N[i].cov = -1;}void update(int i, int L, int R, int val){	if (N[i].l == L&&N[i].r == R){		clear(i, L, R, val);		N[i].cov = val;		return;	}	if (N[i].cov != -1){		N[i << 1].cov = N[i << 1 | 1].cov = N[i].cov;		N[i].cov = -1;	}	int M = (N[i].l + N[i].r) >> 1;	if (R <= M) update(i << 1, L, R, val);	else if (L > M) update(i << 1 | 1, L, R, val);	else update(i << 1, L, M, val), update(i << 1 | 1, M + 1, R, val);	N[i].cov = -1;	N[i].sum = N[i << 1].sum + N[i << 1 | 1].sum + N[i].delta*(N[i].r - N[i].l + 1);}ll query(int i, int L, int R){	if (N[i].l == L&&N[i].r == R){		return N[i].sum;	}	int M = (N[i].l + N[i].r) >> 1;	if (R <= M) return query(i << 1, L, R) + N[i].delta*(R - L + 1);	else if (L > M) return query(i << 1 | 1, L, R) + N[i].delta*(R - L + 1);	else return query(i << 1, L, M) + query(i << 1 | 1, M + 1, R) + N[i].delta*(R - L + 1);}int main(){	while (cin >> n >> m)	{		build(1, 1, n);		int t, l, r, x;		for (int i = 0; i < m; i++){			scanf("%d%d%d", &t, &l, &r);			if (t == 1) {				scanf("%d", &x);				update(1, l, r, x);			}			else{				printf("%I64d\n", query(1, l, r));			}		}	}	return 0;}

 


联系
我们