首页 > 其他分享 >【luogu CF1396D】Rainbow Rectangles(线段树)

【luogu CF1396D】Rainbow Rectangles(线段树)

时间:2022-10-13 11:36:16浏览次数:103  
标签:nxt mo luogu sum cy CF1396D now Rectangles ll

Rainbow Rectangles

题目链接:luogu CF1396D

题目大意

给你一个 L*L 的矩形,里面有 n 个点,有各自的颜色。
然后问你有多少个端点是整点的矩形可以圈出所有颜色至少有一个点。

思路

考虑枚举区间的边界,枚举上边界。
然后再枚举下边界,然后考虑有多少答案。
(因为这个时候已近 \(n^2\) 了)

然后你发现不能 \(O(1)\),看看 \(O(n)\) 行不行。
首先发现如果 \([l,r]\) 可以,那对于 \(x>r\),\([l,x]\) 都可以。
所以我们对于每个左边界,我们只要能求出最左的满足条件的右边界即可。

然后发现值域很大,所以要离散化,如果 \(x_i,y_i\) 代表离散化之后的位置值,设为 \(f_i\)。
那贡献就是 \((y_i-y_{i-1})(L-f_i+1)\),然后上下端点也可以滑动,所以还有 \((x_{r+1}-x_r)(x_l-x_{l-1})\)。
不过上面那个我们可以拆一下:
\(\sum\limits_{i=1}^m(y_i-y_{i-1})(L-f_i+1)\)
\(\sum\limits_{i=1}^m(y_i-y_{i-1})(L+1)-\sum\limits_{i=1}^m(y_i-y_{i-1})f_i\)
\(y_m(L+1)-\sum\limits_{i=1}^m(y_i-y_{i-1})f_i\)
那问题就是怎么求后面这个,也就是如何求 \(f_i\)。

考虑考虑左边界右移。
那有的颜色会消失,你要找到右边第一个能出现的。
那我们可以设 \(nxt_i\) 为 \(i\) 这一列的所有颜色下一次出现的列的最大值。
然后转移就是 \(f_i+1=\max(f_i,nxt_i)\),那其实就是 \(nxt_i\) 的前缀最大值。

那我们 \(O(n)\) 转移了,也就到了 \(n^3\)。

考虑用下端点下手,能不能比如下端点往下,维护答案之类的。
那往下就是要加点,其实不好搞,我们考虑从下往上枚举下断点,那每次就是删点。
那我们可以用 set 记录每个颜色出现的列的坐标,那删除我们就找到上一个颜色是这一个的列,以及下一个。
如果上一个是 \(bef\),下一个是 \(nxt\),那就是 \([bef+1,nxt]\) 里面的每个 \(x\),\(f_x=\max(f_x,nxt)\)。

那这个我们区间去最大我们可以用线段树来搞。
然后你上面那个 \(\sum\limits_{i=1}^m(y_i-y_{i-1})f_i\) 我们可以给区间赋一个权值为 \(y_r-y_l\),每次赋值贡献要乘上这个东西。
但是最后你要的是区间求和,那我们似乎要用吉司机线段树?
其实不用,因为这个 \(f_x\) 显然有着单调的性质,那我们直接二分出贡献的区间,然后直接变成区间赋值就好了。

时间复杂度是 \(n\log^2n\)。

代码

#include<set>
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#define ll long long
#define mo 1000000007 

using namespace std;

const ll N = 2005;
ll n, k, L, x[N], y[N], xn, yn;
vector <pair<ll, ll> > cx[N];
vector <ll> cy[N];
ll ans;

struct node {
	ll x, y, c;
}e[N];
multiset <ll> S, s[N];
ll nxt[N], R[N];

struct XD_tree {
	ll f[N << 2], lzy[N << 2], maxn[N << 2], sz[N << 2];
	
	void up(ll now) {
		f[now] = (f[now << 1] + f[now << 1 | 1]) % mo;
		maxn[now] = max(maxn[now << 1], maxn[now << 1 | 1]);
	}
	
	void downc(ll now, ll x) {
		f[now] = sz[now] * x % mo;
		maxn[now] = x; lzy[now] = x;
	}
	
	void down(ll now, ll l, ll r) {
		ll mid = (l + r) >> 1;
		if (lzy[now] != -1) {
			downc(now << 1, lzy[now]); downc(now << 1 | 1, lzy[now]);
			lzy[now] = -1;
		}
	}
	
	ll find(ll now, ll l, ll r, ll k) {//第一个大于 k 的位置
		if (l == r) return (maxn[now] > k) ? l : r + 1;
		down(now, l, r); ll mid = (l + r) >> 1;
		if (maxn[now << 1] > k) return find(now << 1, l, mid, k);
			else return find(now << 1 | 1, mid + 1, r, k);
	}
	
	void change(ll now, ll l, ll r, ll L, ll R, ll va) {
		if (L <= l && r <= R) {
			downc(now, va); return ;
		}
		down(now, l, r); ll mid = (l + r) >> 1;
		if (L <= mid) change(now << 1, l, mid, L, R, va);
		if (mid < R) change(now << 1 | 1, mid + 1, r, L, R, va);
		up(now);
	}
	
	void change_(ll L, ll R, ll va) {
		if (L > R) return ; ll pl = min(R, find(1, 1, yn, va) - 1);
		if (L <= pl) change(1, 1, yn, L, pl, va);
	}
	
	void build(ll now, ll l, ll r) {
		lzy[now] = -1;
		if (l == r) {
			sz[now] = y[l] - y[l - 1]; maxn[now] = R[l]; f[now] = maxn[now] * sz[now] % mo; return ;
		}
		ll mid = (l + r) >> 1;
		build(now << 1, l, mid); build(now << 1 | 1, mid + 1, r);
		up(now); sz[now] = (sz[now << 1] + sz[now << 1 | 1]) % mo;
	}
}T;

void work(ll l) {
	for (ll i = 1; i <= yn; i++) cy[i].clear();
	for (ll i = l; i <= xn; i++)
		for (ll j = 0; j < cx[i].size(); j++)
			cy[cx[i][j].first].push_back(cx[i][j].second);
	S.clear();
	for (ll i = 1; i <= k; i++) {
		nxt[i] = yn + 1; S.insert(nxt[i]);
		s[i].clear(); s[i].insert(0); s[i].insert(nxt[i]);
	}
	for (ll i = yn; i >= 1; i--) {
		for (ll j = 0; j < cy[i].size(); j++) {
			S.erase(S.find(nxt[cy[i][j]]));
			nxt[cy[i][j]] = i;
			S.insert(nxt[cy[i][j]]);
			s[cy[i][j]].insert(i);
		}
		R[i] = y[*(--S.end())];
	}
	T.build(1, 1, yn);
	
	for (ll r = xn; r >= l; r--) {
		ll sum = (1ll * y[yn] * (L + 1) % mo - T.f[1] + mo) % mo;
		(ans += sum * (x[r + 1] - x[r]) % mo * (x[l] - x[l - 1]) % mo) %= mo;
		for (ll i = 0; i < cx[r].size(); i++) {
			ll col = cx[r][i].second, Y = cx[r][i].first;
			s[col].erase(s[col].find(Y));
			ll bef = *(--s[col].lower_bound(Y));
			ll nxt = *s[col].lower_bound(Y);
			T.change_(bef + 1, Y, y[nxt]);
		}
	}
}

int main() {
	scanf("%lld %lld %lld", &n, &k, &L);
	for (ll i = 1; i <= n; i++) {
		ll z; scanf("%lld %lld %lld", &x[i], &y[i], &z);
		x[i]++; y[i]++; e[i] = (node){x[i], y[i], z};
	}
	
	sort(x + 1, x + n + 1); xn = unique(x + 1, x + n + 1) - x - 1; x[xn + 1] = L + 1;
	sort(y + 1, y + n + 1); yn = unique(y + 1, y + n + 1) - y - 1; y[yn + 1] = L + 1;
	
	for (ll i = 1; i <= n; i++) {
		ll X = lower_bound(x + 1, x + xn + 1, e[i].x) - x;
		ll Y = lower_bound(y + 1, y + yn + 1, e[i].y) - y;
		cx[X].push_back(make_pair(Y, e[i].c));
	}
	
	for (ll i = 1; i <= xn; i++) work(i);
	printf("%lld", ans);
	
	return 0;
}

标签:nxt,mo,luogu,sum,cy,CF1396D,now,Rectangles,ll
From: https://www.cnblogs.com/Sakura-TJH/p/luogu_CF1396D.html

相关文章

  • Luogu P3469 [POI2008]BLO-Blockade
    [P3469POI2008]BLO-Blockade-洛谷|计算机科学教育新生态(luogu.com.cn)图\(G\)本身联通。删除\(u\)的连边后会形成\(k\ge2\)个连通块(至少会把\(u\)隔离出......
  • Luogu2167 Bill的挑战 - 容斥 - dp -
    题目链接:https://www.luogu.com.cn/problem/P2167题解:摘录一段描述容斥题目的话:本题中,关于容斥系数,可以先感性理解一下,严格证明可以用即除了自身,自身的超集都计算......
  • Luogu P6157 有趣的游戏(平衡树 + 树链剖分)
    有趣的游戏题目描述游戏在一棵大小为\(n\)的树上进行。其中每个点都有点权,第\(i\)个点的点权为\(w_i\)。每一次系统会给出一条链,小A可以从这条链上找出两个点权......
  • 【luogu CF1553F】Pairwise Modulo(树状数组)(根号分治)
    PairwiseModulo题目链接:luoguCF1553F题目大意给你一个序列,对于每个前缀,要你求两两互相取模的结果的和。思路考虑新加入一个数增加的答案。那就是加两个部分:\(\sum......
  • Luogu P6880 [JOI 2020 Final] オリンピックバス 题解
    [P6880JOI2020Final]オリンピックバス-洛谷|计算机科学教育新生态(luogu.com.cn)两条前置知识:在图\(G\)上构造根为\(x\)的最短路树\(T\),我们删除任意一条......
  • AC自动机+DP luoguP4052 and P3311
    https://www.luogu.com.cn/problem/P4052题意:求长度为m的小写字母组成的字符串ss中包含给定字符串集合S中任意一个为子串的ss个数。思路:经典的在ac自动机上跑dp的套路,......
  • Luogu P3389【模板】高斯消元法
    题意给定一个线性方程组,对其求解。$1\leqn\leq100,\left|a_i\right|\leq{10}^4,\left|b\right|\leq{10}^4$题解因为之前贺题解的时候没有理解高斯-约......
  • LuoguP3377 【模板】左偏树(可并堆)
    题意如题,一开始有\(n\)个小根堆,每个堆包含且仅包含一个数。接下来需要支持两种操作:1xy:将第\(x\)个数和第\(y\)个数所在的小根堆合并(若第\(x\)或第\(y\)个......
  • luogu P6155 修改题解
    P6155题解闲话这是本蒟蒻写的第三篇题解了,前两篇都因为种种原因报废了,求管理过╥﹏╥正片大家好,我是一名STL选手,于是我用了大量STL+O2的代码过了这道题分析我的代码与......
  • luogu P3571 [POI2014]SUP-Supercomputer
    题面传送门感觉考场上不一定做得出来的题目?首先我们可以得到每个点的深度,然后猜测这个只和每个层的深度有关。我们考虑这样一个贪心:对于每一层的每个点,如果这个点有子节......