POJ2155

因为最近准备模板,所以把不太常用的算法又熟悉了一边,发现果然不练不行。
二维线段树,树套树
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
int n,m;
struct nodey
{
    int l,r,num;
};
struct nodex
{
    int l,r;
    nodey y[1005<<2];
}tree[1005<<2];
void buildy(int l,int r,int pos,int now)
{
    tree[pos].y[now].l=l;
    tree[pos].y[now].r=r;
    tree[pos].y[now].num=0;
    if(l==r)return ;
    int mid=(l+r)>>1;
    buildy(l,mid,pos,now<<1);
    buildy(mid+1,r,pos,now<<1|1);
}
void buildx(int l,int r,int now)
{
    tree[now].l=l;
    tree[now].r=r;
    buildy(1,n,now,1);
    if(l==r)return ;
    int mid=(l+r)>>1;
    buildx(l,mid,now<<1);
    buildx(mid+1,r,now<<1|1);
}
void queryy(int pos,int y,int now,int &t)
{
	//cout<<tree[pos].l<<" "<<tree[pos].r<<" "<<tree[pos].y[now].l<<" "<<tree[pos].y[now].r<<" "<<tree[pos].y[now].num<<endl;
	t^=tree[pos].y[now].num;
    if(tree[pos].y[now].l==tree[pos].y[now].r)
        return ;
    int mid=(tree[pos].y[now].l+tree[pos].y[now].r)>>1;
    if(y<=mid)
		queryy(pos,y,now<<1,t);
    else
		queryy(pos,y,now<<1|1,t);
}
void queryx(int x,int y,int now,int &t)
{
	queryy(now,y,1,t);
    if(tree[now].l==tree[now].r)
        return ;
    int mid=(tree[now].l+tree[now].r)>>1;
    if(x<=mid)
		queryx(x,y,now<<1,t);
    else
		queryx(x,y,now<<1|1,t);
}
void updatey(int y1,int y2,int pos,int now)
{
    if(tree[pos].y[now].l==y1 && tree[pos].y[now].r==y2)
    {
	//	cout<<"1";
	//	tree[pos].y[now].num++;
        tree[pos].y[now].num=!tree[pos].y[now].num;
        return ;
    }
    int mid=(tree[pos].y[now].l+tree[pos].y[now].r)>>1;
    if(y2<=mid)
    updatey(y1,y2,pos,now<<1);
    else if(y1>mid)
    updatey(y1,y2,pos,now<<1|1);
    else
    {
        updatey(y1,mid,pos,now<<1);
        updatey(mid+1,y2,pos,now<<1|1);
    }
}
void updatex(int x1,int y1,int x2,int y2,int now)
{
    if(tree[now].l==x1 && tree[now].r==x2)
    {
        updatey(y1,y2,now,1);
        return ;
    }
    int mid=(tree[now].l+tree[now].r)>>1;
    if(x2<=mid)
    updatex(x1,y1,x2,y2,now<<1);
    else if(x1>mid)
    updatex(x1,y1,x2,y2,now<<1|1);
    else
    {
        updatex(x1,y1,mid,y2,now<<1);
        updatex(mid+1,y1,x2,y2,now<<1|1);
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        buildx(1,n,1);
        while(m--)
        {
            char ch[5];
            int a,b,c,d;
            scanf("%s",ch);
            if(ch[0]=='C')
            {
                scanf("%d%d%d%d",&a,&b,&c,&d);
                updatex(a,b,c,d,1);
		/*		for(int i=1;i<=3;i++)
				{
					for(int j=1;j<=3;j++)
					{
						cout<<tree[j].y[i].num<<" ";
					}
					cout<<endl;
				}*/
            }
            else
            {
                scanf("%d%d",&a,&b);
				int temp=0;
				queryx(a,b,1,temp);
                printf("%d\n",temp);
            }
        }
		cout<<endl;
    }
    return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ1656

    比较水的题,数据量暴力可破,但是你以为这样就结束了吗? 如果数据量大一点呢?不得不说,平时做题还是应该深入一点。 我是在写二维线段树找手感的时候做到这题的,顺势...

    triplebee
  • HDU4027

    本以为对线段树还是比较熟悉的,但是这题改变了我的想法。 顺着wk的题解做了这题。 拿到手就知道线段树,写完T,这时候我想起来蓝桥杯的线段树也是这样的吧,只不过那...

    triplebee
  • 主席树POJ2104

    求区间第k大数是多少 用我惯用的线段树写法似乎不适合写主席树,看别人的代码好半天才看懂 用root表示每一个前缀树的根,思想大致是由第i-1个树构成的树建第i个...

    triplebee
  • 回文素数

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • LintCode 加一题目分析代码

    样例 给定[1,2,3] 表示 123, 返回[1,2,4] . 给定[9,9,9] 表示 999, 返回[1,0,0,0]

    desperate633
  • epoll()函数总结

    http://www.cnblogs.com/Anker/archive/2013/08/17/3263780.html

    bear_fish
  • Java容器(List、Set、Map)知识点快速复习手册

    容器主要包括 Collection 和 Map 两种,Collection 又包含了 List、Set 以及 Queue。

    后端技术漫谈
  • HashMap 和 currentHashMap 终于总结清楚了!

    通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为O(n),当然,对于有序数组,则可采用二分查找,插值查找,斐波那契查找等方式,可将查...

    Java技术栈
  • 基于Windows 10平台的PM2.5检测器制作

        本篇文章详细讲解了如何利用SDS011激光式PM2.5传感器、HC-06蓝牙模块和Windows 10设备完成一个简单的PM2.5检测器及其应用程序的开...

    ShiJiong
  • FHQ Treap小结(神级数据结构!)

    首先说一下, 这个东西可以搞一切bst,treap,splay所能搞的东西 pre 今天心血来潮, 想搞一搞平衡树, 先百度了一下平衡树,发现正宗的平衡树写法应...

    attack

扫码关注云+社区

领取腾讯云代金券