[NOIP2022] 比赛

0
15011418730 LV 7 @ 2025-8-24 22:43:16
自动搬运

查看原文

来自洛谷，原作者为

FutaRimeWoawaSete
Dear the f**king destiny!

搬运于2025-08-24 22:43:16，当前版本为作者最后更新于2022-12-31 18:16:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

sol of P8868

恕我直言，此题的难点在于构造双半群模型，如果只是讲解维护的信息，那么可以看懂此题，但是若在之后碰到类似的题目却还是只能瞎构造半天导致浪费大量时间，导致痛失其他题的分。

本篇题解想大致探索一下幺半群信息构造的方法，但并不是极其严谨与科学，你可以理解成民科吧！主要是市面上没有啥讲信息构造的，如果你做题不多其实很容易被坑。

一些极其一眼的思考：扫描线，然后转化成带历史和的 $X_{i} \times Y_{i}$ ，修改操作是二元信息区间覆盖，信息是求和，盲猜可做，于是难点来到如何设计双半群模型，构造信息。

从自己博客里搬点东西过来。

半群

给定一个集合 $D$ 以及一个集合 $D$ 上的二元运算 $\times$ 满足 $D \times D \rightarrow D$ 。

对于该运算满足结合律：$a,b,c \in D,(a \times b)\times c = a \times (b \times c)$。

幺半群

给定一个集合 $D$ 以及一个集合 $D$ 上的二元运算 $\times$ 满足 $D \times D \rightarrow D$ 。

对于该运算满足结合律：$a,b,c \in D,(a \times b)\times c = a \times (b \times c)$。

满足幺元存在使得：$a,\epsilon \in D,a \times \epsilon = \epsilon \times a = a$。

交换半群

给定一个集合 $D$ 以及一个集合 $D$ 上的二元运算 $\times$ 满足 $D \times D \rightarrow D$ 。

对于该运算满足结合律：$a,b,c \in D,(a \times b)\times c = a \times (b \times c)$。

对于该运算满足交换律： $a,b,c \in D,a \times b = b \times a$ 。

范围

常见的范围有序列区间，树简单路径，二维平面矩形，高维正交范围，半平面范围，圆范围。

我们一般理解成对于进行修改和查询的信息的限制。

双半群模型

直接再次贺一下 lxl PPT 里的图。

还需要注意的是对于 $D \times M \rightarrow D$ 的 $\times$ 运算对于 $(D,+)$ 运算具有分配律。

我们称这样的模型为双半群模型。

需要注意的是，采取线段树，维护的信息至少是半群信息，然而大多数时候也是交换半群信息。

那么我们需要做到的是设计 $D,M$ 去满足上述的双半群模型，在大多数时候我们采取的下传标记信息都是维护 $D$ 的增量，根据题意也应当适当添加其它下传标记信息像区间覆盖区间乘法等等，此题就是区间覆盖。

我们根据一些表象的信息，比如这里有区间覆盖，那我们知道我们的下传标记信息至少有一个 $c_x,c_y$ 表示对于区间 $x$ 元和 $y$ 元的覆盖。

其次尝试构造 $D$ 。我们先来尝试一些区间覆盖的影响，假设一直修改 $x$ 那么貌似我们可以加 $\sum y$ 这样的东西。当然如果你要套路化，在观察到 $X_i \times Y_i$ 这样的结构的时候就可以以此为最高次，构造一个多项式形式的 $D$ 类信息，即维护扫描线时当前的 $\sum X_i \times Y_i,\sum X_i,\sum Y_i$ 以及 $s$ 表示区间历史和 $len$ 表示区间长，形式化地记为 $D = (s_{xy},s_x,s_y,s,len)$ 。

对于下传标记的信息，通过尝试修改带来的影响，或者放弃思考，套路化地设成 $M = (c_x,c_y,m_{xy},m_x,m_y,m)$ ，表示区间覆盖 $x/y$ ，在该合并信息 $M$ 中的覆盖标记未下传前，对于子树内 $D$ 中 $s$ 的贡献需要加上 $m_{xy} \times D_{s_{xy}} + m_x \times D_{s_{x}} + m_y \times D_{s_y} + m \times D_{len}$。

定义下传标记信息中对于贡献加法的优先级高于覆盖标记是有理由的，比如说纯区间覆盖，区间加，区间求和，一种实现方法就是下传信息时先让加标记下传，然后再下传区间覆盖标记，因为加标记的信息依赖于未被覆盖之前的区间信息，你让覆盖标记优先于加法标记下传就会让加标记无所依赖，难以维护。

在大多数时候，你要相信你通过常规的标记设计出来的 $D,M$ 是满足 $D$ 是交换半群和半群信息的，以防万一你可以验证一下。

所以只需要构造出来三类关系，$D \times M \rightarrow D,D + D \rightarrow D,M \text * M \rightarrow M$ 的具体操作就好了。

构造难度基本和 $D,M$ 的维护标记个数正相关。此题你发现 $D + D \rightarrow D$ 就是最简单的！写成代码就是：
```
inline info merge(info x,info y){return info(x.s + y.s , x.sx + y.sx , x.sy + y.sy , x.sxy + y.sxy);}	
```
其次我们构造 $D \times M \rightarrow D$ ，直接放代码然后解释：
```
inline info merge(info x,tag y,int len)
{
	x.s += y.axy * x.sxy + y.ax * x.sx + y.ay * x.sy + y.c * len;
	if(y.cx && y.cy)
	{
		x.sxy = len * y.cx * y.cy;
		x.sx = len * y.cx;
		x.sy = len * y.cy;
	}
	else if(y.cx)
	{
		x.sxy = x.sy * y.cx;
		x.sx = len * y.cx;
	}
	else if(y.cy)
	{
		x.sxy = x.sx * y.cy;
		x.sy = len * y.cy;
	}
	return x;
}
```
即对于 $s$ 我们根据定义先直接更新一遍；然后再根据是否有覆盖标记修改 $s_{xy},s_x,s_y$ ，这个比较简单就不多说了。

最后我们构造 $M \text{*} M \rightarrow M$ 。

还是贴代码解释：
```
inline tag merge(tag x,tag y)//x -> y
{ 
	if(y.cx && y.cy) y.c += x.axy * y.cx * y.cy + x.ax * y.cx + x.ay * y.cy + x.c;
	else if(y.cx) 
	{
		y.ay += x.axy * y.cx + x.ay;
		y.c += x.c + x.ax * y.cx;
	}
	else if(y.cy)
	{
		y.ax += x.axy * y.cy + x.ax;
		y.c += x.c + x.ay * y.cy;
	}
	else 
	{
		y.axy += x.axy;
		y.ax += x.ax;
		y.ay += x.ay;
		y.c += x.c;
	}
	if(x.cx) y.cx = x.cx;
	if(x.cy) y.cy = x.cy;
	return y;
}
```
$M1 \text{*} M2 \rightarrow M$ ，设 $M1$ 作用在 $M2$ 上，设区间长为 $len$ ，分类讨论：
- 若 $M2$ 中的 $c_x,c_y$ 都有值，我们不妨转化为对于每个位置增量的形式( $D_m$ )，则当前的状态就是区间内的 $X_i,Y_i$ 都相同，考虑贡献是 ${M1}_{m_{xy}} \times \sum X_i \times Y_i$ ，由于 $X_i,Y_i$ 都相等，变成 ${M1}_{m_{xy}} \times {M2}_{c_x} \times M2_{c_y} \times len$，则增量是 ${M1}_{m_{xy}} \times {M2}_{c_x} \times M2_{c_y}$ 。类似地我们写出来其它三个增量即可。
- 若仅 $M2$ 中的 $c_x$ 有值，对于 ${M1}_{m_{xy}} \times \sum X_i \times Y_i$ 我们写成 ${M1}_{m_{xy}} \times M2_{c_x} \times \sum Y_i$ ，发现对于 $\sum Y_i$ 就又可以迭代下去，将 ${M1}_{m_{xy}} \times M2_{c_x}$ 加到 $M2_{m_y}$ 上面去即可；而对于 $M1_{m_x} \times \sum X_i$ 我们写成 $M1_{m_x} \times M2_{c_x} \times len$ 的形式，即将 $M1_{m_x} \times M2_{c_x}$ 加到 $M2_{m_c}$ 上面去；然后 $M2_{m_y} \leftarrow M2_{m_y} + M1_{m_y},M2_{m_c} \leftarrow M2_{m_c} + M1_{m_c}$。
- 若仅 $M2$ 中的 $c_y$ 有值类似上述情况；
- 若 $M2$ 中的 $c_x,c_y$ 都无值，就直接对应项相加即可。
在 $M1 \text{*} M2 \rightarrow M$ 构造时，个人认为最重要的一点是，根据分讨的情况我们要转化式子，然后将已经确定的常数项根据下传标记的定义分配到更低次幂的增量上。

一个卡常的办法是一次单调栈弹栈过程进行到底，不要弹一次区间修改一次；将 $D,M$ 单独定义成结构体会方便调试一些。

当然如果你神通广大，直接写成矩乘然后拆拆拆也是可以的。

时间复杂度 $O((n + q) \log n)$ 。

单根做法相对有点平凡，而且很容易被卡常就没有讲的必要了？
```
#include "bits/stdc++.h"
using namespace std;
const int Len = 2.5e5 + 5;
#define ull unsigned long long
ull n,q;
inline ull read() {
    char ch = getchar();
    ull x = 0, f = 1;
    while (ch < '0' || ch > '9') ch = getchar();
    while ('0' <= ch && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
void write(ull x) {
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
struct info
{
	ull s,sx,sy,sxy;
	info(){s = sx = sy = sxy = 0;}
	info(ull S,ull SX,ull SY,ull SXY){s = S , sx = SX , sy = SY , sxy = SXY;}
	inline void clr(){s = sx = sy = sxy = 0;}
	inline void output(){printf("%llu %llu %llu %llu\n",s,sx,sy,sxy);}
}inf[Len << 2];
struct tag
{
	ull cx,cy,ax,ay,axy,c;
	tag(){cx = cy = ax = ay = axy = c = 0;}
	tag(ull CX,ull CY,ull AX,ull AY,ull AXY,ull C){cx = CX , cy = CY , ax = AX , ay = AY , axy = AXY , c = C;}
	inline void clr(){cx = cy = ax = ay = axy = c = 0;}
	inline bool empty(){return !(cx || cy || ax || ay || axy || c);}
	inline void output(){printf("%llu %llu %llu %llu %llu %llu\n",cx,cy,ax,ay,axy,c);}
}tg[Len << 2];
//需要实现 O + T -> O,T + T -> T,O + O -> O
//重点在于 T + T -> T 
//若 c_x,c_y 都存在，则当前的标记维护的是 cx,cy 的信息，只需要将信息叠加到 c 上即可
//若 c_x 存在，则当前 ay,c 会被影响， 
//若 c_y 存在，则当前 ax,c 会被影响，
//若都不存在，含义就是暴力更新 
//每次结束后下传一个 axy = 1 的 tag
//emmmm。
inline info merge(info x,info y){return info(x.s + y.s , x.sx + y.sx , x.sy + y.sy , x.sxy + y.sxy);}	
inline tag merge(tag x,tag y)//x -> y
{ 
	if(y.cx && y.cy) y.c += x.axy * y.cx * y.cy + x.ax * y.cx + x.ay * y.cy + x.c;
	else if(y.cx) 
	{
		y.ay += x.axy * y.cx + x.ay;
		y.c += x.c + x.ax * y.cx;
	}
	else if(y.cy)
	{
		y.ax += x.axy * y.cy + x.ax;
		y.c += x.c + x.ay * y.cy;
	}
	else 
	{
		y.axy += x.axy;
		y.ax += x.ax;
		y.ay += x.ay;
		y.c += x.c;
	}
	if(x.cx) y.cx = x.cx;
	if(x.cy) y.cy = x.cy;
	return y;
}
inline info merge(info x,tag y,int len)
{
	x.s += y.axy * x.sxy + y.ax * x.sx + y.ay * x.sy + y.c * len;
	if(y.cx && y.cy)
	{
		x.sxy = len * y.cx * y.cy;
		x.sx = len * y.cx;
		x.sy = len * y.cy;
	}
	else if(y.cx)
	{
		x.sxy = x.sy * y.cx;
		x.sx = len * y.cx;
	}
	else if(y.cy)
	{
		x.sxy = x.sx * y.cy;
		x.sy = len * y.cy;
	}
	return x;
}
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
inline void push_up(int p){inf[p] = merge(inf[ls(p)] , inf[rs(p)]);}
inline void push_down(int p,int l,int r)
{
	if(!tg[p].empty())
	{
		int mid = (l + r) >> 1;int l1 = (mid - l + 1) , l2 = (r - mid);
		tg[ls(p)] = merge(tg[p] , tg[ls(p)]) , tg[rs(p)] = merge(tg[p] , tg[rs(p)]);
		inf[ls(p)] = merge(inf[ls(p)] , tg[p] , l1) , inf[rs(p)] = merge(inf[rs(p)] , tg[p] , l2);
		tg[p].clr();
		return;
	}
}
void update(int p,int l,int r,int nl,int nr,tag t)
{
	if(nl <= l && nr >= r) 
	{
		tg[p] = merge(t , tg[p]);
		inf[p] = merge(inf[p] , t , r - l + 1);
		//printf("#%d %d:\n",l,r);
		//tg[p].output();
		//inf[p].output();
		return;
	}
	push_down(p , l , r);
	int mid = (l + r) >> 1;
	if(nl <= mid) update(ls(p) , l , mid , nl , nr , t);
	if(nr > mid) update(rs(p) , mid + 1 , r , nl , nr , t);
	push_up(p);
}
ull query(int p,int l,int r,int nl,int nr)
{
	if(nl <= l && nr >= r) 
	{
		/*if(l == 2 && r == 2)
		{
			printf("?%d %d:\n",l,r);
			tg[p].output();
			inf[p].output();
		}*/
		return inf[p].s;
	}
	push_down(p , l , r);
	int mid = (l + r) >> 1;ull res = 0;
	if(nl <= mid) res += query(ls(p) , l , mid , nl , nr);
	if(nr > mid) res += query(rs(p) , mid + 1 , r , nl , nr);
	return res;
}
ull a[Len],b[Len],stk[Len][2],top[2];
struct Node
{
	ull l,id;
	Node(){l = id = 0;}
	Node(ull L,ull ID){l = L , id = ID;}
}Qs[Len];
vector<Node> vec[Len];
ull Pt[Len];ull sz[Len];
signed main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int TP = read();
	n = read();
	for(int i = 1 ; i <= n ; i ++) a[i] = read();
	for(int i = 1 ; i <= n ; i ++) b[i] = read();
	q = read();
	for(int i = 1 ; i <= q ; i ++)
	{
		Qs[i].l = read() , Qs[i].id = read();
		sz[Qs[i].id] ++;
	}
	for(int i = 1 ; i <= n ; i ++) vec[i].reserve(sz[i]);
	for(int i = 1 ; i <= q ; i ++) vec[Qs[i].id].push_back(Node(Qs[i].l , i));
	for(int i = 1 ; i <= n ; i ++)
	{
		while(top[0] > 0 && a[stk[top[0]][0]] < a[i]) top[0] --;
		update(1 , 1 , n , stk[top[0]][0] + 1 , i , tag(a[i] , 0 , 0 , 0 , 0 , 0));
		stk[++ top[0]][0] = i;
		while(top[1] > 0 && b[stk[top[1]][1]] < b[i]) top[1] --;
		update(1 , 1 , n , stk[top[1]][1] + 1 , i , tag(0 , b[i] , 0 , 0 , 0 , 0));
		stk[++ top[1]][1] = i;
		update(1 , 1 , n , 1 , i , tag(0 , 0 , 0 , 0 , 1 , 0));
		int Sz = (int)vec[i].size();for(int j = 0 ; j < Sz ; j ++) Pt[vec[i][j].id] = query(1 , 1 , n , vec[i][j].l , i);	
	} 
	for(int i = 1 ; i <= q ; i ++) write(Pt[i]) , putchar('\n');
	return 0;
}
```

ID

3193

时间

2000ms

内存

512MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

信息

还没有账户？

登录