首页 > 其他分享 >CF641E Little Artem and Time Machine 题解

CF641E Little Artem and Time Machine 题解

时间:2024-08-09 20:38:38浏览次数:13  
标签:Little another 题解 pos long mid Machine pd define

题目传送门

前置知识

CDQ 分治

解法

单点修改区间查询,但值域巨大,考虑离散化掉 \(x\)。

时刻 \(t\) 仍很大,考虑将其作为 CDQ 分治的第一维,然后套个 CDQ 分治即可,注意及时清空桶数组。

代码

CodeForces 275382150

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
struct node
{
	int pd,pos,val,col,id;
	bool operator < (const node &another) const
	{
		return (pos==another.pos)?(pd>another.pd):(pos<another.pos);
	}
}a[300010],tmp[300010];
int b[300010],ans[300010],sum[300010],cnt=0,q_cnt=0;
void add(int pd,int pos,int val,int col,int id)
{
	cnt++;
	a[cnt].pd=pd;
	a[cnt].pos=pos;
	a[cnt].val=val;
	a[cnt].col=col;
	a[cnt].id=id;
}
void cdq(int l,int r)
{
	if(l>=r)
	{
		return;
	}
	int mid=(l+r)/2,x=l,y=mid+1,pos=l;
	cdq(l,mid);
	cdq(mid+1,r);
	while(x<=mid&&y<=r)
	{
		if(a[x]<a[y])
		{
			sum[a[x].col]+=a[x].pd*a[x].val;
			tmp[pos]=a[x];
			pos++;
			x++;
		}
		else
		{
			ans[a[y].id]+=a[y].val*sum[a[y].col];
			tmp[pos]=a[y];
			pos++;
			y++;
		}
	}
	while(x<=mid)
	{
		tmp[pos]=a[x];
		pos++;
		x++;
	}
	while(y<=r)
	{
		ans[a[y].id]+=a[y].val*sum[a[y].col];
		tmp[pos]=a[y];
		pos++;
		y++;
	}
	for(int i=l;i<=mid;i++)
	{
		sum[a[i].col]=0;
	}
	for(int i=l;i<=r;i++)
	{
		a[i]=tmp[i];
	}
}
int main()
{
	int n,pd,t,x,i;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>pd>>t>>x;
		b[i]=x;
		if(pd==1)
		{
			add(1,t,1,x,0);
		}
		if(pd==2)
		{
			add(1,t,-1,x,0);
		}
		if(pd==3)
		{
			q_cnt++;
			add(0,t,1,x,q_cnt);
		}
	}
	sort(b+1,b+1+n);
	b[0]=unique(b+1,b+1+n)-(b+1);
	for(i=1;i<=n;i++)
	{
		a[i].col=lower_bound(b+1,b+1+b[0],a[i].col)-b;
	}
	cdq(1,cnt);
	for(i=1;i<=q_cnt;i++)
	{
		cout<<ans[i]<<endl;
	}
	return 0;
} 

标签:Little,another,题解,pos,long,mid,Machine,pd,define
From: https://www.cnblogs.com/The-Shadow-Dragon/p/18351458

相关文章

  • CF1209E2 Rotate Columns (hard version) 题解
    CF1209E2给定\(n\timesm\)的矩阵,可以对每一列进行若干次循环移位,求操作完成后每一行的最大值之和的最大值。\(1\leqn\leq12,1\leqm\leq2000\)这里\(m\)很大,但有一个很重要的性质这\(m\)列中只有最大的前\(n\)个会对答案产生贡献因此我们直接就把......
  • 【题解】ABC365(A~E)
    前四题30min切,然后T5死磕70min+几发小唐错,距离比赛结束还有16s交最后一发,AC了。目录A.LeapYear题目描述思路代码B.SecondBest题目描述思路代码C.TransportationExpenses题目描述思路代码D.AtCoderJanken3题目描述思路代码E.XorSigmaProblem题目描述思路代码A.Lea......
  • CF908E New Year and Entity Enumeration 题解
    CF908E给定\(m\),令\(M=2^m-1\)。给定\(\{0,1,\cdots,M\}\)的大小为\(n\)的子集\(T\),定义集合\(T\subseteqS\subseteq\{0,1,\cdots,M\}\)是好的当且仅当:\(a\inS\Rightarrowa\oplusM\inS\)\(a,b\inS\Rightarrowa\and\b\inS......
  • 题解:CF1209E1 Rotate Columns (easy version)
    题目传送门题意给出一个\(n\timesm\)的矩阵,我们可以对每一列进行循环位移,不限次数,最后求每一行的最大值之和。\(1\leqn\leq4,1\leqm\leq100\)思路注意到\(n\)的范围很小,那么我们也可以缩小\(m\)的范围。正确的方案显然是取整个矩阵的前\(n\)大值,并且将它......
  • CF1647F Madoka and Laziness 题解
    CF1647F给定排列\(p\),将其划分为两个单峰子序列,求两个单峰子序列的峰的组合的情况数。\(2\leqn\leq5\times10^5\)首先要注意到一个非常常见的地方:两个单峰子序列中的一个的峰值一定在整个排列\(p\)的最大值处这个非常显然,但并不注意到他的重要性,容易被忽视为......
  • 2024牛客暑期多校训练营8 I Haitang and Ranking 题解
    乱搞看到\(n=1e5\),时限3s,存在修改操作,很自然的想到根号分治。考虑按照时间分治。对每\(B\)个交换统一处理,\(B\)个交换最多有\(2B\)个元素改变状态,剩下都不变。那么只要对这\(2B\)元素内,暴力枚举,剩下的元素构建数据结构实现二维数点,平面内区间最值。因为\(a,b\)是不......
  • 《DNK210使用指南 -CanMV版 V1.0》第十八章 machine.Timer类实验
    第十八章machine.Timer类实验1)实验平台:正点原子DNK210开发板2)章节摘自【正点原子】DNK210使用指南-CanMV版V1.03)购买链接:https://detail.tmall.com/item.htm?&id=7828013987504)全套实验源码+手册+视频下载地址:http://www.openedv.com/docs/boards/k210/ATK-DNK210.html5......
  • luogu题解:P10456 The Pilots Brothers' refrigerator【缺少 SPJ】
    思路此题题意酷似P10449.费解的开关。https://www.luogu.com.cn/problem/P10449不同之处便是状态连锁改变不同,但做法截然不同,此题是一个\(4\times4\)的矩阵。暴力枚举的复杂度是\(O(10^7)\),即\(2^{16}\times16\times16=16777216\),\(10^7\)的复杂度可以通......
  • P2901题解
    题目大意输出一张有向带权图前k短路的长度思路分析这是道k短路板子题我们可以用Astar算法来实现它OIwiki相关算法的网页简单来讲,Astar定义了一个估值函数f(x)=g(x)+h(x)g(x)表示由起点到达x点的路程(不一定是最短路),而h(x)则是终点到x点的最短路程这个估值函数可以预估从该......
  • Codeforces 165E Compatible Numbers 题解
    思路高维前缀和高维前缀和把数的二进制看成一个集合,二进制的每一位为\(1\)为全集\(V\)。根据题目描述,若两数\(a,b\)相容,则\(a\operatorname{and}b=0\),容易发现,\(b\in\complement_{V}a\),所以我们只需要用高维前缀和处理出\(\complement_{V}a\)的一个元素即可。......