首页 > 其他分享 >poj2777(线段树)

poj2777(线段树)

时间:2023-04-14 23:27:23浏览次数:61  
标签:ch int 线段 read poj2777 query include define

Count Color

POJ - 2777

<iframe frameborder="0" height="2048px" id="frame-description" scrolling="no" src="https://vjudge.csgrandeur.cn/problem/description/1465294586?1681268590000" style="box-sizing: inherit; height: 1157.39px" width="100%"></iframe>

思路:暴力能过,线段树维护这个区间的颜色,如果是混色则置为1,如果是单一颜色则设为这个颜色,修改就是正常的区间修改,区间查询就要变一下。还有题解是用二进制做得,可以学一下。

#define _CRT_SECURE_NO_WARNINGS 1
#include<algorithm>
#include<fstream>
#include<iostream>
#include<cstdio>
#include<deque>
#include<string>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
//#include<unordered_map>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 310000
#define N 210100
#define endl '\n'
#define exp 1e-8
#define lc p << 1
#define rc p << 1|1
#define lowbit(x) ((x)&-(x))
const double pi = acos(-1.0);
typedef long long LL;
typedef unsigned long long ULL;
inline LL read() {
	ULL x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
struct tree
{
	int l, r,v,tag;  //v代表颜色,tag是标记
}tr[4 * N];
int n, t, m;
int ha[50];  
void pushup(int p)
{
	if (tr[lc].v == tr[rc].v)  //如果左右区间颜色一样,则为一样
		tr[p].v = tr[lc].v;
	else tr[p].v = 0; //否则置为0
}
void pushdown(int p)  //标记下传
{
	if (tr[p].tag)
	{
		tr[lc].v = tr[rc].v = tr[p].tag;
		tr[lc].tag = tr[rc].tag = tr[p].tag;
		tr[p].tag = 0;
	}
}
void build(int p, int l, int r)
{
	tr[p].l = l, tr[p].r = r;
	if (l == r) { tr[p].v = 1;  return; }
	int m = l + r >> 1;
	build(lc, l, m);
	build(rc, m + 1, r);
	pushup(p);
}
void update(int p, int x, int y, int k)
{
	if (tr[p].v == k)return;  //一个小小的剪枝,当要修改的区间颜色就是c时,直接返回不用修改
	if (x <= tr[p].l && tr[p].r <= y)
	{
		tr[p].v = k;
		tr[p].tag = k;
		return;
	}
	pushdown(p);
	int m = tr[p].l + tr[p].r >> 1;
	if (x <= m)update(lc, x, y, k);
	if (y > m)update(rc, x, y, k);
	pushup(p);
}
void query(int p, int x, int y)
{
	if (tr[p].v!=0)  //如果不为0,则表示为纯色
	{
		if (x <= tr[p].l && tr[p].r <= y)
		{
			ha[tr[p].v] = 1;
			return;
		}
	}
	pushdown(p);
	int m = tr[p].l + tr[p].r >> 1;   //为0就分裂
	if (x <= m) query(lc, x, y);
	if (y > m)  query(rc, x, y);
}
int main()
{
	n = read(), t = read(), m = read();
	build(1, 1, n);
	for (int i = 1; i <= m; i++)
	{
		char a;
		cin >> a;
		if (a == 'C')
		{
			int x, y, c;
			x = read(), y = read(), c = read();
			if (x > y)swap(x, y);
			update(1, x, y, c);
		}
		else if(a=='P')
		{
			int x, y;
			x = read(), y = read();
			if (x > y)swap(x, y);
		    int ans = 0;
			memset(ha, 0, sizeof(ha));
			query(1, x, y);
			for (int i = 1; i <= 40; i++)
			{
				if (ha[i])ans++;
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}

标签:ch,int,线段,read,poj2777,query,include,define
From: https://www.cnblogs.com/wyh344866/p/17320209.html

相关文章

  • 线段树(单点修改,区间查询)
    题目描述如题,已知一个数列,你需要进行下面两种操作:将某一个数加上 x求出某区间每一个数的和输入格式第一行包含两个正整数 n,m,分别表示该数列数字的个数和操作的总个数。第二行包含 n 个用空格分隔的整数,其中第 i 个数字表示数列第 i 项的初始值。接下来 ......
  • POJ 2299 Ultra-QuickSort(线段树+离散化)
    题目地址:POJ2299这题曾经用归并排序做过,线段树加上离散化也可以做。一般线段树的话会超时。这题的数字最大到10^10次方,显然太大,但是可以利用下标,下标总共只有50w。可以从数字大的开始向树上加点,然后统计下标比它小即在它左边的数的个数。因为每加一个数的时候,比该数大的数已经加完......
  • POJ 3468 A Simple Problem with Integers(线段树区间更新)
    题目地址:POJ3468打了个篮球回来果然神经有点冲动。。无脑的狂交了8次WA。。居然是更新的时候把r-l写成了l-r。。。这题就是区间更新裸题。区间更新就是加一个lazy标记,延迟标记,只有向下查询的时候才将lazy标记向下更新。其他的均按线段树的来就行。代码如下:#include<iostream>#in......
  • HDU 1166 敌兵布阵(线段树)
    题目地址:HDU1166听说胡浩版的线段树挺有名的。于是就拜访了一下他的博客。详情戳这里。于是就完全仿照着胡浩大牛的风格写的代码。至于原理,鹏鹏学长已经讲的再清晰不过了。我就在下面的代码注释中将原理说明一下吧。来纪念第一发线段树。下面是代码+注释。#include<iostream>#in......
  • ZOJ 3886 Nico Number (线段树)
    题目地址:ZJU3886这个题需要想到一点,因为对一个数x不断取模的话,而且设定他小于模才会进行取余操作的话,那么最多只会进行logx次,因为每次取模都会使x最少折半。然后想到了这点就很好做了。对于区间取模更新操作可以直接暴力更新,维护一个最大值,如果这个区间的最大值小于模的话,就......
  • CAD如何测量连续线段长度?CAD测量连续线段长度步骤
    在CAD绘图过程中,经常会绘制一些连续的线段,如果想要知道这些连续线段长度的话,该怎么操作吗?CAD如何测量连续线段长度?下面小编就以浩辰CAD软件为例来给大家分享一下CAD测量连续线段长度的具体操作步骤吧!CAD测量连续线段长度步骤:浩辰CAD软件中已经考虑到了这种需求,在CAD测量命令(DIST......
  • 线段树区间和,区间修改,区间查询板子
    #include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;#definelson(nd<<1)#definerson(nd<<1|1)#definemid(l+r>>1)constintN=1e5+5;intsum[N<<2],lazy[N<<2];inta[N];voidbuild(intnd,in......
  • 广州大学第十七届ACM大学生程序设计竞赛 L. 因子模仿 - hard version 线段树维护矩阵
    传送门大致思路:  观察发现,茉美香胜利会叠加对手所有状态,茉美香失败会被对手叠加所有状态。我们可以用矩阵[a1,a2,b1,b2]表示两个人的状态(其中a1,a2表示茉美香,b1,b2表示对手)茉美香赢了之后的状态是[a1+b1,a2+b2,b1,b2],茉美香输了之后的状态是[a1,b1,a1+b1,......
  • 线段树之扫描线
    P5490【模板】扫描线给你n个位于平面直角坐标系上的长方形,它们之间可能互相重叠,求这些长方形的面积。很显然,对于长方形之间有重叠部分,如果采用容斥原理,不仅非常复杂,而且难以实现。事实上,既然题目已经给了我们这些长方形的顶点,这些长方形最终构成的图形可以被坐标轴划分为m......
  • 线段树分治
    线段树分治线段树分治,解决的是这样一类问题:有一个时间轴,有一些操作,这些操作在时间轴上每一个的作用范围是一个区间;在某些时间或者全局询问一些关于操作效果的问题。它的重要效果是:一是可以把所有删除操作改成撤回操作(也就是撤回当前最近一个操作,而不是删除之前随便一个操作),可以......