首页 > 其他分享 >崩坏：星穹铁道

崩坏：星穹铁道

时间：2023-07-11 14:45:35浏览次数：23  
标签：Insert qus 星穹 int 线段 铁道 崩坏 now sum

题解

对于 \(20\%\) 的数据：

直接暴力 \(O(n^3)\) 枚举即可。

对于 \(35\%\) 的数据：

不妨将有交的矩形连边，不难发现最终需要统计反图中三元环个数，考虑原图中任意三个点的关系：

设上述情况在原图中的出现次数分别为 \(x_1, x_2, x_3, x_4\) ，那么我们需要求解 \(x_1\) ，容易发现 \(x_1+x_2+x_3+x_4=\binom{n}{3}\) ，考虑统计每个点的度数 \(deg_i\) ，并求解 \(\sum deg_i(n-deg_i-1)\) ，容易发现这实际上等于 \(2x_2+2x_3\) ，由于特殊性质保证 \(x_4=0\) ，因此直接暴力建图进行统计即可。

复杂度 \(O(n^2)\) 。

对于 \(50\%\) 的数据：

考虑快速求解每个点的度数，由于 \(deg_i\) 为与矩形 \(i\) 有交的矩形个数，因此考虑扫描线解决原问题。

我们分两种情况讨论：

  1. \(l_j<l_i\) ，我们在 \(l_j\) 的位置插入线段 \([u_j, v_j]\) ，在 \(r_j\) 的位置删除线段 \([u_j, v_j]\) ，容易发现只需要在 \(l_i\) 位置上统计与 \([u_i, v_i]\) 相交的线段个数，可以通过计算 \(v_j<u_i\) 和 \(u_j>v_i\) 的线段个数求解。

  2. \(l_j>l_i\) ，我们在 \(l_j\) 的位置插入线段 \([u_j, v_j]\) ，不难发现我们查询的是满足 \(l_i<l_j<r_i\) 并且 \([u_j, v_j]\) 与 \([u_i, v_i]\) 有交的线段个数，将询问简单差分后很容易查询。

使用树状数组维护，复杂度 \(O(n\log n)\) 。

对于 \(100\%\) 的数据：

考虑快速统计原图中三元环的个数。

假设对于三元组 \((i, j, k)\) ，满足矩形 \(i, j, k\) 两两有交，考虑在 \(\max(l_i, l_j, l_k)\) 的位置统计答案，具体来讲，仍然使用扫描线解决问题，一个矩形 \(x\) ，我们在 \(l_x\) 插入线段 \([u_x, v_x]\) ，在 \(r_x\) 删除线段 \([u_x, v_x]\) ，如果我们的线段树可以快速维护集合中相交的线段对数，那么我们可以在插入 \((i, j, k)\) 三元组中最后一条线段前查询集合中相交线段对数，将最后一条线段插入，再次查询集合中相交线段对数，这样我们可以求解与当前插入线段有交的相交线段对数，也就是包含当前矩形的一部分三元环，由于一组三元环一定会在最后一个矩形被插入的位置被统计到，因此可以保证正确性。

考虑维护这棵线段树，对于一组相交的线段，比较自然的想法是在相交的位置统计其贡献，因此考虑维护 \(val_i=\sum_{x\in S}[l_x\le i\le r_x], val'_i=\sum_{x\in S}[l_x\le i<r_x]\) ，那么相交线段对数为 \(\sum\binom{val_i}{3}-\sum\binom{val'_i}{3}\) ，设当前这对相交的线段相交部分长度为 \(l\) ，容易发现这对线段会对 \(l\) 个位置的 \(val_i\) 产生贡献，对 \(l-1\) 个位置的 \(val'_i\) 产生贡献，因此直接相减可以将当前相交线段的贡献恰好统计一次。

那么线段树只需要支持区间修改即可。

考虑如何下放懒惰标记，容易发现这等价于快速求解 \(\binom{x+y}{t}\) ，简单展开有：

\[\binom{x+y}{t}=\sum_{k=0}^{t}\binom{x}{k}\binom{y}{t-k} \]

由于 \(y\) 可能为负数，因此需要使用广义二项式。

直接在线段树每个节点维护 \(\sum \binom{val_i}{t}, t\le 3\) 即可快速下方懒惰标记。

总复杂度 \(O(n\log n)\) ，当然常数飞天。

按照理论上界来讲，线段树每个节点维护信息达到 \(O(n^4)\) 级别，因此需要使用 __int128 ，但由于出题人十分善良，因此并没有卡这个上界。（才不是因为不会卡呢！）

code

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int max1 = 2e5;

int n;
struct Matrix
{
	int X1, X2, Y1, Y2, id;
}matrix[max1 + 5];
int save[max1 * 2 + 5], lenx, leny;
int degree[max1 + 5];
long long ans;
long long cnt;

struct Bit
{
	int tree[max1 * 2 + 5], lim;

	#define lowbit(now) ( now & -now )

	void Clear ( int __lim )
	{ lim = __lim; memset(tree + 1, 0, sizeof(int) * __lim); return; }

	void Insert ( int now, int x )
	{
		while ( now <= lim )
		{
			tree[now] += x;
			now += lowbit(now);
		}
		return;
	}

	int Query ( int now )
	{
		int res = 0;
		while ( now )
		{
			res += tree[now];
			now -= lowbit(now);
		}
		return res;
	}

	int Query ( int L, int R )
	{ return Query(R) - Query(L - 1); }
}Tree1, Tree2;
int sum;

long long C ( int n, int m )
{
	long long res = 1;
	for ( int i = 1; i <= m; i ++ )
		res = res * ( n - i + 1 );
	for ( int i = 1; i <= m; i ++ )
		res = res / i;
	return res;
}

struct Segment_Tree
{
	#define lson(now) ( now << 1 )
	#define rson(now) ( now << 1 | 1 )

	struct Data
	{
		long long sum[2][4];
		int tag[2];
	}tree[max1 * 8 + 5];

	void Build ( int now, int L, int R )
	{
		memset(tree[now].sum, 0, sizeof(tree[now].sum));
		tree[now].sum[0][0] = tree[now].sum[1][0] = R - L + 1;
		tree[now].tag[0] = tree[now].tag[1] = 0;
		if ( L == R )
			return;

		int mid = L + R >> 1;
		Build(lson(now), L, mid);
		Build(rson(now), mid + 1, R);
		return;
	}

	void Update ( int now, int x, int num )
	{
		Data tmp = tree[now];
		long long d[4] = { C(x, 0), C(x, 1), C(x, 2), C(x, 3) };
		for ( int i = 0; i < 4; i ++ )
		{
			tree[now].sum[num][i] = 0;
			tree[now].sum[num ^ 1][i] = tmp.sum[num ^ 1][i];
			for ( int k = 0; k <= i; k ++ )
				tree[now].sum[num][i] += tmp.sum[num][k] * d[i - k];
		}
		tree[now].tag[num] = tmp.tag[num] + x;
		tree[now].tag[num ^ 1] = tmp.tag[num ^ 1];
		return;
	}

	void Push_Up ( int now )
	{
		for ( int i = 0; i < 4; i ++ )
		{
			tree[now].sum[0][i] = tree[lson(now)].sum[0][i] + tree[rson(now)].sum[0][i];
			tree[now].sum[1][i] = tree[lson(now)].sum[1][i] + tree[rson(now)].sum[1][i];
		}
		return;
	}

	void Push_Down ( int now )
	{
		if ( tree[now].tag[0] )
			Update(lson(now), tree[now].tag[0], 0), Update(rson(now), tree[now].tag[0], 0);
		if ( tree[now].tag[1] )
			Update(lson(now), tree[now].tag[1], 1), Update(rson(now), tree[now].tag[1], 1);
		tree[now].tag[0] = tree[now].tag[1] = 0;
		return;
	}

	void Insert ( int now, int L, int R, int ql, int qr, int x, int num )
	{
		if ( L >= ql && R <= qr )
			return Update(now, x, num);

		Push_Down(now);
		int mid = L + R >> 1;
		if ( ql <= mid )
			Insert(lson(now), L, mid, ql, qr, x, num);
		if ( qr > mid )
			Insert(rson(now), mid + 1, R, ql, qr, x, num);
		Push_Up(now);
		return;
	}

	long long Query ( int num )
	{
		return tree[1].sum[num][3];
	}
}Tree3;

struct Question
{
	int L, R, id;

	Question () {}
	Question ( int __L, int __R, int __id )
	{ L = __L, R = __R, id = __id; }
};

int add1[max1 * 2 + 5], add2[max1 * 2 + 5];
Question qus[max1 * 2 + 5];

int main ()
{
	scanf("%d", &n);
	for ( int i = 1; i <= n; i ++ )
		scanf("%d%d%d%d", &matrix[i].X1, &matrix[i].X2, &matrix[i].Y1, &matrix[i].Y2), matrix[i].id = i;

	for ( int i = 1; i <= n; i ++ )
		save[i] = matrix[i].X1, save[n + i] = matrix[i].X2;
	sort(save + 1, save + 1 + n + n); lenx = unique(save + 1, save + 1 + n + n) - (save + 1);
	for ( int i = 1; i <= n; i ++ )
		matrix[i].X1 = lower_bound(save + 1, save + 1 + lenx, matrix[i].X1) - save, 
	matrix[i].X2 = lower_bound(save + 1, save + 1 + lenx, matrix[i].X2) - save;

	for ( int i = 1; i <= n; i ++ )
		save[i] = matrix[i].Y1, save[n + i] = matrix[i].Y2;
	sort(save + 1, save + 1 + n + n); leny = unique(save + 1, save + 1 + n + n) - (save + 1);
	for ( int i = 1; i <= n; i ++ )
		matrix[i].Y1 = lower_bound(save + 1, save + 1 + leny, matrix[i].Y1) - save, 
	matrix[i].Y2 = lower_bound(save + 1, save + 1 + leny, matrix[i].Y2) - save;

	for ( int i = 1; i <= lenx; i ++ )
		add1[i] = add2[i] = 0, qus[i] = Question(0, 0, 0);

	for ( int i = 1; i <= n; i ++ )
	{
		add1[matrix[i].X1] = matrix[i].Y1;
		add1[matrix[i].X2] = -matrix[i].Y1;

		add2[matrix[i].X1] = matrix[i].Y2;
		add2[matrix[i].X2] = -matrix[i].Y2;

		qus[matrix[i].X1] = Question(matrix[i].Y1, matrix[i].Y2, matrix[i].id);
	}

	Tree1.Clear(leny), Tree2.Clear(leny), sum = 0;
	for ( int i = 1; i <= lenx; i ++ )
	{
		if ( qus[i].id )
			degree[qus[i].id] += sum - Tree1.Query(qus[i].R + 1, leny) - Tree2.Query(1, qus[i].L - 1);
		if ( add1[i] )
		{
			if ( add1[i] > 0 )
				Tree1.Insert(add1[i], 1), ++sum;
			else
				Tree1.Insert(-add1[i], -1), --sum;
		}
		if ( add2[i] )
		{
			if ( add2[i] > 0 )
				Tree2.Insert(add2[i], 1);
			else
				Tree2.Insert(-add2[i], -1);
		}
	}

	for ( int i = 1; i <= lenx; i ++ )
		add1[i] = add2[i] = 0, qus[i] = Question(0, 0, 0);
	for ( int i = 1; i <= n; i ++ )
	{
		add1[matrix[i].X1] = matrix[i].Y1;
		add2[matrix[i].X1] = matrix[i].Y2;

		qus[matrix[i].X1] = Question(matrix[i].Y1, matrix[i].Y2, -matrix[i].id);
		qus[matrix[i].X2] = Question(matrix[i].Y1, matrix[i].Y2, matrix[i].id);
	}

	Tree1.Clear(leny), Tree2.Clear(leny), sum = 0;
	for ( int i = 1; i <= lenx; i ++ )
	{
		if ( qus[i].id )
		{
			if ( qus[i].id > 0 )
				degree[qus[i].id] += sum - Tree1.Query(qus[i].R + 1, leny) - Tree2.Query(1, qus[i].L - 1) - 1;
			else
				degree[-qus[i].id] -= sum - Tree1.Query(qus[i].R + 1, leny) - Tree2.Query(1, qus[i].L - 1);
		}

		if ( add1[i] )
			Tree1.Insert(add1[i], 1), ++sum;
		if ( add2[i] )
			Tree2.Insert(add2[i], 1);
	}

	for ( int i = 1; i <= lenx; i ++ )
		qus[i] = Question(0, 0, 0);

	for ( int i = 1; i <= n; i ++ )
		qus[matrix[i].X2] = Question(matrix[i].Y1, matrix[i].Y2, -matrix[i].id);

	for ( int i = 1; i <= n; i ++ )
		qus[matrix[i].X1] = Question(matrix[i].Y1, matrix[i].Y2, matrix[i].id);

	Tree3.Build(1, 1, leny);

	for ( int i = 1; i <= lenx; i ++ )
	{
		if ( qus[i].id )
		{
			if ( qus[i].id > 0 )
			{
				cnt -= Tree3.Query(0) - Tree3.Query(1);
				Tree3.Insert(1, 1, leny, qus[i].L, qus[i].R, 1, 0);
				Tree3.Insert(1, 1, leny, qus[i].L, qus[i].R - 1, 1, 1);
				cnt += Tree3.Query(0) - Tree3.Query(1);
			}
			else
			{
				Tree3.Insert(1, 1, leny, qus[i].L, qus[i].R, -1, 0);
				Tree3.Insert(1, 1, leny, qus[i].L, qus[i].R - 1, -1, 1);
			}
		}
	}

	for ( int i = 1; i <= n; i ++ )
		ans += 1LL * degree[i] * ( n - degree[i] - 1 );

	ans = C(n, 3) - (ans >> 1) - cnt;
	printf("%lld\n", ans);

	return 0;
}

标签：Insert,qus,星穹,int,线段,铁道,崩坏,now,sum
From： https://www.cnblogs.com/KafuuChinocpp/p/17497163.html

相关文章

  • 石家庄铁道大学 王建民 软件工程 上课心得
    软件工程是一项涵盖广泛的领域，我们在课程中学习了许多知识和技能，其中包括软件项目管理、软件开发生命周期、需求分析、设计原则、编码实践、测试策略以及架构模式等重要内容。以下是我对这些主题的一些总结和心得体会： 软件项目管理软件项目管理是软件工程过程中必不可少的环节......
  • 石家庄铁道大学自动评教脚本
    写（抄）了半个下午，科技是第一生产力！Object.defineProperty(navigator,'userAgent',{value:'Android',writable:false});varnum=document.getElementById("tempGrid").rows.length-1console.log('共'+num+'门课')vari=1;vartim......
  • 玻璃之花与崩坏的世界
    PKUSC2023游记Day0由于下雨所以火车晚点\(1\)个小时，到达北京后几乎一直在摆烂，中间尝试看过杜教筛和PAM，然而确实看不下去，实际上考试也没有用到。Day1早上去北大参加开幕式，之后试机写了后缀数组和NTT的板子，后缀数组对拍时调了半天才过，感觉下午要寄。之后去未名湖边散......
  • 星穹
    ......
  • 自由意志的崩坏
    自由意志的崩坏主导西方世界的是自由主义的各种思想：个人主义、人权、民主、自由市场。然而21世纪的科学正在破坏自由主义秩序的基础。科学的进步破坏了自由意志这一事实。......
  • 石家庄铁道大学选课系统
    石家庄铁道大学学生选课管理系统（50分） 1、项目需求：石家庄铁道大学为了提高教务处的工作效率，方便用户之间信息的交流，简化学生选课的流程，使选课管理工作更规范化，系统化，程序......
  • 17级19年期末考试----石家庄铁道大学学生选课管理系统（50分）
         2017级《JAVA语言程序设计》  上机考试试题                2019.01.10  考试要求 一、本试卷为2017......
  • 石家庄铁道大学2022年秋季开学考试总结
     java开学第一节课，我们亲爱的建民老师给我们准备了一套题目，在暑假时我们已经自学了一部分内容，但是突如其来的考试还是让我乱了阵脚，主要是熟练度不高，只完成了一些基础的项......
  • 石家庄铁道大学在校学生行程统计
    石家庄铁道大学在校学生行程统计（20分）考试时间：180分钟1、项目需求：为了有效防止新冠疫情的传播，急需开发一套在校学生行程统计系统，完成信息统计，提前准备，有效保护在校学生的......
  • 石家庄铁道大学2022年秋季 2021 级课堂测试试卷（一）（15分）
    石家庄铁道大学2022年秋季  2021 级课堂测试试卷（一）（15分）课程名称： JAVA语言程序设计  任课教师：王建民       考试时间： 150分钟  一、考试要求：1、......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99