POJ1656

比较水的题,数据量暴力可破,但是你以为这样就结束了吗?

如果数据量大一点呢?不得不说,平时做题还是应该深入一点。

我是在写二维线段树找手感的时候做到这题的,顺势就写了,虽然烦了一点,但是加深了对二维线段树的理解。

不会四分树,只会树套树,洋洋洒洒3500B的代码

/****************************************************
   file name: 1656.cpp
   author: huangjipeng
   creat time: 2014年09月22日 星期一 21时14分58秒
***************************************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ls (now<<1)
#define rs (ls|1)
#define mid ((x[now].l+x[now].r)>>1)
#define MAXN 1
typedef long long ll;
struct node
{
	int l,r,num,flag;//懒惰标记,虽然不用也没事,但是搞ACM的一定得精益求精
};
struct x
{
	int l,r;
	node y[105<<2];
}x[105<<2];
void buildy(int l,int r,int now,int pos)
{
	x[pos].y[now].l=l;
	x[pos].y[now].r=r;
	x[pos].y[now].num=0;
	x[pos].y[now].flag=0;
	if(l==r)return ;
	int mia=(l+r)>>1;
	buildy(l,mia,now<<1,pos);
	buildy(mia+1,r,now<<1|1,pos);
}
void buildx(int l,int r,int now)
{
	x[now].l=l;
	x[now].r=r;
	buildy(1,100,1,now);
	if(l==r)return ;
	buildx(l,mid,ls);
	buildx(mid+1,r,rs);
}
void down(int pos,int now)
{
	x[pos].y[ls].flag=x[pos].y[rs].flag=x[pos].y[now].flag;
	if(x[pos].y[now].flag==1)
	{
		x[pos].y[ls].num=x[pos].y[rs].num=0;
	}
	else
	{
		x[pos].y[ls].num=(x[pos].y[ls].r+1-x[pos].y[ls].l);
		x[pos].y[rs].num=(x[pos].y[rs].r+1-x[pos].y[rs].l);
	}
	x[pos].y[now].flag=0;
}
void updatey(int y1,int y2,int pos,int now,int col)
{
	if(x[pos].y[now].l==y1 && x[pos].y[now].r==y2)
	{
		x[pos].y[now].flag=col;
		if(col==1)
			x[pos].y[now].num=0;
		else
			x[pos].y[now].num=(x[pos].r+1-x[pos].l)*(y2+1-y1);
		return ;
	}
	if(x[pos].y[now].flag>0)down(pos,now);
	int mia=(x[pos].y[now].l+x[pos].y[now].r)>>1;
	if(y2<=mia)
		updatey(y1,y2,pos,ls,col);
	else if(y1>mia)
		updatey(y1,y2,pos,rs,col);
	else
	{
		updatey(y1,mia,pos,ls,col);
		updatey(mia+1,y2,pos,rs,col);
	}
	x[pos].y[now].num=(x[pos].y[ls].num+x[pos].y[rs].num);
}
void updatex(int x1,int y1,int x2,int y2,int now,int col)
{
	if(x[now].l==x1 && x[now].r==x2 && x2==x1)//横坐标退化成点,防止区域重合,也可以区间查询,写完才发现,不想改了
	{
		updatey(y1,y2,now,1,col);
		return ;
	}
	if(x2<=mid)
		updatex(x1,y1,x2,y2,ls,col);
	else if(x1>mid)
		updatex(x1,y1,x2,y2,rs,col);
	else
	{
		updatex(x1,y1,mid,y2,ls,col);
		updatex(mid+1,y1,x2,y2,rs,col);
	}
}
int queryy(int y1,int y2,int now,int pos)
{
	if(x[pos].y[now].l==y1 && x[pos].y[now].r==y2)
	{
	//	cout<<x[pos].y[now].num<<endl;
		return x[pos].y[now].num;
	}
	if(x[pos].y[now].flag>0)down(pos,now);
	int mia=(x[pos].y[now].l+x[pos].y[now].r)>>1;
	if(y2<=mia)
		return queryy(y1,y2,ls,pos);
	else if(y1>mia)
		return queryy(y1,y2,rs,pos);
	else
	{
		return queryy(y1,mid,ls,pos)+queryy(mid+1,y2,rs,pos);
	}
}
int queryx(int x1,int y1,int x2,int y2,int now)
{
	if(x[now].l==x1 && x[now].r==x2 && x1==x2)
	{
		return queryy(y1,y2,1,now);
	}
	if(x2<=mid)
		return queryx(x1,y1,x2,y2,ls);
	else if(x1>mid)
		return queryx(x1,y1,x2,y2,rs);
	else
		return queryx(x1,y1,mid,y2,ls)+queryx(mid+1,y1,x2,y2,rs);
}
int main()
{
	int t;
	buildx(1,100,1);
	cin>>t;
	while(t--)
	{
		char ch[10];
		int a,b,c;
		scanf("%s%d%d%d",ch,&a,&b,&c);
		if(ch[0]=='W')
		{
			updatex(a,b,a+c-1,b+c-1,1,1);
	/*		for(int i=1;i<6;i++)
			{
				for(int j=1;j<6;j++)
				{
					cout<<x[j].y[i].num<<" ";
				}
				cout<<endl;
			}
			cout<<endl;*/
		}
		else if(ch[0]=='B')
		{
			updatex(a,b,a+c-1,b+c-1,1,2);
		/*	for(int i=1;i<6;i++)
			{
				for(int j=1;j<6;j++)
				{
					cout<<x[j].y[i].num<<" ";
				}
				cout<<endl;
			}
			cout<<endl;*/
		}
		else
		{
			printf("%d\n",queryx(a,b,a+c-1,b+c-1,1));
		}
	}
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ2155

    因为最近准备模板,所以把不太常用的算法又熟悉了一边,发现果然不练不行。 二维线段树,树套树 #include<iostream> #include<cstdio...

    triplebee
  • leetcode 6 ZigZag Conversion

    The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of...

    triplebee
  • Leetcode 140 Word Break II

    Given a string s and a dictionary of words dict, add spaces in s to construct a...

    triplebee
  • 基础练习 FJ的字符串

      FJ在沙盘上写了这样一些字符串:   A1 = “A”   A2 = “ABA”   A3 = “ABACABA”   A4 = “ABACABAD...

    刘开心_1266679
  • 玩转VSCode-完整构建VSCode开发调试环境

    目前使用VS2019开发.NET Core应用,一直有一个想法,在VS Code中复刻VS的开发环境,同时迁移到VS Code。

    李明成
  • BZOJ3998: [TJOI2015]弦论(后缀自动机)

    第二行为两个整数T和K,T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。

    attack
  • Reduce 和 Transduce 的含义

    学习函数式编程,必须掌握很多术语,否则根本看不懂文档。 本文介绍两个基本术语:reduce和transduce。它们非常重要,也非常有用。 ? 一、reduce...

    ruanyf
  • RecyclerView定制:通用ItemDecoration及全展开RecyclerView的实现不同场景RecyclerView实现

    看书的小蜗牛
  • 安装BBR加速脚本为服务器提速

    BBR 是 Google 开源的 TCP BBR 拥塞控制算法,并提交到了 Linux 内核,最新的 4.10 版内核已经用上了该算法。 主要用于网络加速,类似...

    周俊辉
  • 12-系统教程演示(WIFI模块)

    https://www.cnblogs.com/yangfengwu/p/9955765.html

    杨奉武

扫码关注云+社区

领取腾讯云代金券