Luogu P5445 [APIO2019] 路灯

标签：==   print   main   node   api   cst   单点   insert   ++i   

很清新的DS题，话说我好久没写过DS了……

首先我们考虑把一对路灯\(x,y\)间的答案看做点对\((x,y)\)，那么显然有一个性质，若\(l,r\)联通，则\(u,v(l\le u也联通

换句话说就是\((x,y)\)为最长的连续的1子序列的两个端点，那么每次它会对矩形\((x,x),(y,y)\)内的每个点都造成贡献

我们考虑类似于ODT那样用set维护每个最长的连续的1子序列，这样只需要在切换状态的时候把区间和贡献一起计算即可

很容易发现这里的时间是有可减性的，那么意味着我们只需要求出这个区间上次加入的时间，和当前时间的差值就是它的贡献

现在题目变成了二维平面内的区间修改，单点查询问题，可以CDQ分治+树状数组也可以大力树套树

反正都是\(O(n\log^2n)\)我就写了相对好写的树套树

#include
#include
#define RI register int
#define CI const int&
using namespace std;
const int N=300005;
struct interval
{
	int l,r,t;
	inline interval(CI L=0,CI R=0,CI T=0) { l=L; r=R; t=T; }
	friend bool operator  S;
typedef set :: iterator SI;
class Tree_Array_Segment_Tree
{
	private:
		struct segment
		{
			int ch[2],v;
		}node[N*300]; int rt[N],tot;
		#define lc(x) node[x].ch[0]
		#define rc(x) node[x].ch[1]
		#define V(x) node[x].v
		#define TN CI l=1,CI r=n
		inline void _modify(int& now,CI beg,CI end,CI mv,TN)
		{
			if (!now) now=++tot; if (beg>1;
			if (begmid) _modify(rc(now),beg,end,mv,mid+1,r);
		}
		inline int _query(CI now,CI pos,TN)
		{
			if (!now) return 0; if (l==r) return V(now); int mid=l+r>>1;
			return (posl,it->r,it->l,it->r,tim-it->t),r=it->r,S.erase(it);
	if (s[x-1]==‘1‘) it=find(x-1),T.modify(it->l,it->r,it->l,it->r,tim-it->t),l=it->l,S.erase(it);
	S.insert(interval(l,r,tim)); s[x]=‘1‘;
}
inline void Off(CI tim,CI x)
{
	SI it=find(x); int l=it->l,r=it->r,t=it->t; T.modify(l,r,l,r,tim-t); S.erase(it);
	if (l!=x) S.insert(interval(l,x-1,tim)); if (r!=x) S.insert(interval(x+1,r,tim)); s[x]=‘0‘;
}
inline int Ext(CI tim,CI l,CI r)
{
	if (s[l]==‘0‘) return 0; SI it=find(l);
	return rr?tim-it->t:0;
}
int main()
{
	RI i; for (scanf("%d%d%s",&n,&q,s+1),i=1;i

Luogu P5445 [APIO2019] 路灯

标签：==   print   main   node   api   cst   单点   insert   ++i   

原文地址：https://www.cnblogs.com/cjjsb/p/13379318.html