9.23 小记

9.23 模拟赛

没啥好说的

就枚举子集警钟敲烂：

for(int j=i;j;j=(j-1)&i)

没了，题答和骗分过样例谁乐意写谁写反正我不写

[Code+#3]寻找车位

线段树+单调队列

首先是暴力的话，先是枚举右上角，然后用单调队列找最靠左的最大符合要求的正方形。

然后考虑带修和多次询问。

由于他保证 \(m\leq n\) ,所以 \(m\leq 2\times 10^3\) ，所以 \(O(qm\log n)\) 是可以接受的。所以我们可以考虑把 \(n\) 这一维放到线段树上。

这样我们可以在线段树的节点上暴力像刚才说的那样搜索，然后我们需要考虑怎样合并左右节点。

大概就是这样：

--------------- x=l
0 0 0 0 0 1 1 0
1 0 1 1 0 1 1 0
1 0 0 1 0 0 1 0
1 1 1 1 1 1 1 1
--------------- x=mid
1 1 1 1 1 1 1 1
1 1 1 1 0 1 0 1
0 1 1 1 1 0 1 1
1 0 0 0 1 0 0 1
--------------- x=r

在两侧节点内部的节点中的答案我们已经考虑完了，现在我们要考虑跨 \(mid\) 的答案。

参考最大子段和的思路，我们设对于 \(p\) 节点上，纵列为 \(i\) ，从上到下延伸的最多的 \(1\) 为 \(up_{p,i}\) ，从下至上延伸的最多的 \(1\) 为 \(down_{p,i}\) 。这样我们只需要找到一段区间内左儿子\(down\) 的最小值，右儿子 \(up\) 的最小值的和比区间长度大就行了。

我们把上面那个矩阵压一下

--------------- x=l
3 1 1 3 1 1 4 1
--------------- x=mid
2 3 3 2 1 2 1 3
--------------- x=r

这样我们对于每一个 \(y\) 都需要找到最大的正方形。

单调队列就可以用上了。

查询的时候可以利用 \(0\) 位置的节点合并，能少好多空间。（好像之前的题也能这么办）

然后还有个东西就是可以把中括号重载的。

struct node
{
    int val[160050002];
    int* operator [] (int x)
    {
        return val+x*m;
    }
}up,down,mx;

这样二维数组就能压成一维的。

然后我把合并的代码扔上去吧

void merge(int p,int ls,int rs,int l,int r,int L,int R)
{
	int lx1=1,rx1=0;int lx2=1,rx2=0;int j=l;
	for(int i=l;i<=r;i++)
	{
		while(lx1<=rx1&down[ls][q1[rx1]]>down[ls][i]) rx1--;q1[++rx1]=i;
		while(lx2<=rx2&up[rs][q2[rx2]]>up[rs][i]) rx2--;q2[++rx2]=i;
		while(lx1<=rx1&&lx2<=rx2&down[ls][q1[lx1]]+up[rs][q2[lx2]]<(i-j+1)) 
		{
			if(q1[lx1]==j) lx1++;
			if(q2[lx2]==j) lx2++;
			j++;
		}
		mx[p][i]=max({i-j+1,mx[ls][i],mx[rs][i]});
	}
	for(int i=1;i<=m;i++)
	{
		up[p][i]=up[ls][i]+(up[ls][i]==(L)?up[rs][i]:0);
		down[p][i]=down[rs][i]+(down[rs][i]==(R)?down[ls][i]:0);
	}
	return;
}

闲话

今天效率好低好低。

为啥就我一个人在做基础算法啊。

为啥他们在做生成函数和群论啊，那是人做的吗。果然还是我太菜了。

QAQ

下午 Zpair 出去带了一瓶雪碧回来，把晚上的我救活了。

如果说所有悲欢终将在喧嚣中淹没

总有人与我不期而遇在迷茫的路口

为我再次寻回遗失在现实角落的梦

为世界带来久违的温柔

风的欢笑雨的哭声

融化裹挟了谁平凡的感动

身后闪烁万家灯火

将人间的故事诉说给星空

无论春夏无论秋冬

无论多少岁月将我们分隔

摘下耳机时眼眶依旧会微红

戴上耳机依旧是你描绘的梦