莫队算法相关

分块?

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 17   Accepted Submission(s) : 6

Font: Times New Roman | Verdana | Georgia

Font Size:

Problem Description

  给定n个数,记为ai(1<=i <= n),求区间内某两个数和为给定的sum的对数。

Input

  第一行输入整数T,表示共有T组.
  接下来共T组,首先输入n,sum分别表示共n个数以及给定的和,再下一行依次输入n个数ai,然后输入一个q,表示共有q个询问,接下来q行每行输入l,r,表示要求的是区间[l,r].

范围:
T<=20
n <= 20000,sum <= 20000
1 <= ai < sum
q <= 20000,1<= l < r <= n

Output

  输出q行,回答每个询问的值.

Sample Input

1
4 4
1 2 2 3
3
1 2
2 3
1 4

Sample Output

0
1
2

Source

test

关于莫队算法,个人觉得这篇讲的比较通俗易懂,关于复杂度上界O(n^1.5)也证明的比较详细。。(大致上来说就是按左边界分块且每块内按右边界排列之后,将每次r的转移最坏O(n),变成一个块内的询问转移完毕最坏O(n),l的转移总复杂度可以类似分析)
真正的莫队算法是要求最小曼哈顿生成树的,但是其实有一种简洁的分块方法,具体见上面链接中的文章
其实突然发现自己以前是碰到过这种分块题目的,在一片论文中讲了一种支持修改的动态rmq算法,就是分块的,每次询问时sqrt(n),自己还写了模板,坑爹啊,全忘光了。。
这里还是简述下怎么分块:将长度为n的数列划分成每段长为sqrt(n)的一些段,这样可以保证复杂度上界是O(n^1.5)(当然前提是单步转移是O(1),如果是lgn,那么总复杂度是O((n^1.5)*lgn))。证明见上面说的文章,里面讲的很清楚。
这道题的话,数的范围在20000以内,所以可以用一个数组cnt[i],表示数i出现了几次。这样从(l,r)转移到(l,r+1)是O(1)的。像这种单步转移能做到O(1)或者O(lgn)的,都可以用莫队算法来搞。然后先O(n)算出第一个询问的答案,之后转移到第二个询问的时候,要注意如果是较少一个数,也就是差不多(l,r)->(l+1,r)这种转移类型,那么如果data[l]等于sum-data[l]时注意特判,因为这时候减少的对数不是cnt[sum-data[l]],而是cnt[sum-data[l]]-1。(试想,现在有3个2,sum为4,那么有3对数它们的和为4,然后减少一个2,显然减少了2对,而不是3对)

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef struct Query{
    int l,r,g,num,ans;
}Q;
Q q[20010];
int n,sum,data[20010],m;
bool cmp(Q a,Q b)
{
    if(a.g==b.g) return a.r<b.r;
    return a.g<b.g;
}
bool cmp2(Q a,Q b)
{
    return a.num<b.num;
}
int cnt[20010];
void cal(Q &a,Q &b)
{
    int i,tmp=a.ans;
    int l1=a.l,r1=a.r,l2=b.l,r2=b.r;
    if(r1<=l2 || r2<=l1)
    {
        for(i=l1;i<=r1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
        for(i=l2;i<=r2;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
    }
    else if(l1<=l2 && l2<=r1 && r1<=r2)
    {
        for(i=l1;i<=l2-1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
        for(i=r1+1;i<=r2;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
    }
    else if(l2<=l1 && l1<=r2 && r2<=r1)
    {
        for(i=l2;i<=l1-1;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
        for(i=r2+1;i<=r1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
    }
    else if(l1<=l2 && r2<=r1)
    {
        for(i=l1;i<=l2-1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
        for(i=r2+1;i<=r1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
    }
    else
    {
        for(i=l2;i<=l1-1;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
        for(i=r1+1;i<=r2;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
    }
    b.ans=tmp;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&sum);
        memset(cnt,0,sizeof(cnt));
        int len=(int)sqrt(n*1.0);
        //int cnt=(len*len==n?len:len+1);
        for(i=1;i<=n;i++) scanf("%d",&data[i]);
        scanf("%d",&m);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].g=q[i].l/len+1;
            q[i].num=i;q[i].ans=0;
        }
        sort(q+1,q+1+m,cmp);
        for(i=q[1].l;i<=q[1].r;i++) q[1].ans+=cnt[sum-data[i]],cnt[data[i]]++;
        for(i=2;i<=m;i++) cal(q[i-1],q[i]);
        sort(q+1,q+1+m,cmp2);
        for(i=1;i<=m;i++) printf("%d\n",q[i].ans);



    }
    return 0;
}

其他题目:
bzoj2038
poj3241
WC 2013 糖果公园
UVALive 3662 Another Minimum Spanning Tree
hdu5213

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=29469

Time Limit : 4000/2000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 15   Accepted Submission(s) : 2

Font: Times New Roman | Verdana | Georgia

Font Size:

Problem Description

  给你一棵N个节点的树,其中1为根节点,每个节点有权值。一开始所有节点的权值均为0。现在我们要进行M次操作。
  一共有以下两种操作:
  1)1 u d 节点1到节点u的最短路径上的所有的节点(包括1,u)的权值增加d(1<=d<=300)
  2)2 u 查询节点u的权值

Input

  多组测试数据
  每组测试数据第一行有两个数N,M (1<=N,M<=60000)
  接下来N-1行 每行有两个数u,v (1<=u,v<=N且u!=v)表示节点u和节点v之间有一条边
  接下来M行,即M次操作,含义见题目描述

Output

  对于每个操作2,请输出u的权值

Sample Input

3 4
1 2
1 3
1 2 3
2 1
2 2
2 3

Sample Output

3
3
0

Source

test

昨天校赛,这题没想到思路,想到就很简单了。。这题很有意思
思路:如果给某个点加上一个值,从这个点到根的结点都要加上这个值,这样暴力肯定不行。以前做过把树求出dfs序,转化成线段树的题,但是那是对某棵子树的结点都加上一个值,那么这题如果dfs序的话,每次操作要加的那些结点在线段树中时不连续的,怎么解决呢
其实可以这样做,每次操作只修改该点的值,最后求点u的值,只要对以u为根的子树对应的区间求和就行了。。。
当然也可以用树状数组,我比较习惯线段树,虽然慢一些。。

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=6e4+5;
typedef struct Edge{
    int to,next;
}Edge;
typedef struct Node{
    int begin,end;
}Node;
Edge edge[2*maxn];
Node node[maxn];
int head[maxn],cnt;

int sum[maxn<<2];
void pushup(int id)
{
    sum[id]=sum[lson]+sum[rson];
}
void update(int id,int l,int r,int pos,int v)
{
    if(l==r)
    {
        sum[id]+=v;
        return;
    }
    int m=(l+r)/2;
    if(pos<=m) update(lson,l,m,pos,v);
    else update(rson,m+1,r,pos,v);
    pushup(id);
}
int query(int id,int l,int r,int L,int R)
{
    if(L<=l && r<=R)
    {
        return sum[id];
    }
    int m=(l+r)/2;
    int ret=0;
    if(L<=m) ret+=query(lson,l,m,L,R);
    if(R>m) ret+=query(rson,m+1,r,L,R);
    return ret;
}
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
}
int n,m,num;
bool visit[maxn];
void dfs(int cur)
{
    visit[cur]=1;
    node[cur].begin=(++num);
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(visit[v]) continue;
        dfs(v);
    }
    node[cur].end=num;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        int u,v;
        cnt=0;num=0;
        memset(head,-1,sizeof(head));
        memset(visit,0,sizeof(visit));
        memset(sum,0,sizeof(sum));
        for(i=1;i<=n-1;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
        }
        dfs(1);
        int c,x,d;
        for(i=1;i<=m;i++)
        {
            scanf("%d",&c);
            if(c==1)
            {
                scanf("%d%d",&x,&d);
                update(1,1,n,node[x].begin,d);
            }
            if(c==2)
            {
                scanf("%d",&x);
                printf("%d\n",query(1,1,n,node[x].begin,node[x].end));
            }
        }

    }



    return 0;
}

zoj3765 Lights 平衡树

好吧,不得不承认,经过一个寒假的颓废啥都忘了。。
一道裸的splay,但是比赛的时候我一直觉得用splay维护gcd会不会出错。。。。因为我居然觉得旋转过程中gcd无法正确维护。。。。
思路:splay节点信息
on:节点是否是开灯状态
val0:该节点关灯时的值,如果该节点灯开着,那么val0=0,不影响结果。
val1:该节点开灯时的值,如果该节点灯关着,那么val1=0,不影响结果。
gcd0:以该节点为根的子树中所有状态为关的灯的gcd
gcd1:以该节点为根的子树中所有状态为开的灯的gcd
num[0]:以该节点为根的子树有多少个状态为关的灯
num[1]:以该节点为根的子树有多少个状态为开的灯
看来这个月要好好复习了。。。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 500000+100
#define inf 0x3f3f3f3f
inline int max(int a,int b){return a>b?a:b;}
int gcd(int a,int b)
{
    if(a<b) {int t=a;a=b;b=t;}
    return (b==0?a:gcd(b,a%b));
}
struct SplayTree {
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]

	int root;//根节点
	int fa[N];//父亲结点
	int ch[N][2];//孩子结点
	int sz[N];//以结点i为子树的结点数
    int cnt;
    int val0[N],val1[N];
    int on[N];
    int gcd0[N],gcd1[N];
    int data[N],state[N];
    int num[N][2];
	void pushup(int x)
	{
		sz[x]=1+sz[LC]+sz[RC];//如果左子树为空,则LC=0,而sz[0]=0,即如果结点某个结点的子节点不存在,则指向空结点0,空节点的sz=0,不会造成错误
        gcd0[x]=gcd(gcd(gcd0[LC],gcd0[RC]),val0[x]);
        gcd1[x]=gcd(gcd(gcd1[LC],gcd1[RC]),val1[x]);
        num[x][0]=num[LC][0]+num[RC][0]+1-on[x];
        num[x][1]=num[LC][1]+num[RC][1]+on[x];
	}

	void rotate(int x, bool f) //旋转
	{
		int y=fa[x];
		int z=fa[y];
		ch[y][!f]=ch[x][f];
		fa[ch[x][f]]=y;
		fa[x]=z;
		if(z)
		{
			ch[z][ch[z][1]==y]=x;
		}
		ch[x][f]=y;
		fa[y]=x;
		pushup(y);
	}

	void splay(int x, int g) //把结点x转到结点g下
	{
		int y=fa[x];
        while (y!=g)
        {
			int z=fa[y];
			bool f=(ch[y][0]==x);
			if (z!=g && f==(ch[z][0]==y))
			{
				rotate(y,f);
			}
			rotate(x,f);
			y=fa[x];
		}
		pushup(x);
		if(g==0)
		{
			root=x;
		}
	}

	void rotateto(int k,int g) {	//把第k个结点转到结点g下,从第0个开始,因为有附加结点
		int x=root;
		while (sz[LC]!=k)
		{
			if (k<sz[LC])
			{
				x=LC;
			} else
			{
				k-=(sz[LC]+1);
				x=RC;
			}
		}
		splay(x,g);
	}

	void newNode(int &x,int c,int flag)
	{
        x=++cnt;
        on[x]=flag;
        num[x][flag]=1;num[x][1-flag]=0;
        if(!flag) val0[x]=c,val1[x]=0;
        else val1[x]=c,val0[x]=0;
        LC=RC=fa[x]=0;
        gcd0[x]=gcd(gcd(gcd0[LC],gcd0[RC]),val0[x]);
        gcd1[x]=gcd(gcd(gcd1[LC],gcd1[RC]),val1[x]);
        sz[x]=1;
	}

	void makeTree(int &x,int l,int r,int f)
	{
		if (l>r)
		{
			return;
		}
		int m=(l+r)>>1;
		newNode(x,data[m],state[m]);	/*num[m]权值改成题目所需的*/
		makeTree(LC,l,m-1,x);
		makeTree(RC,m + 1,r,x);
		fa[x]=f;
		pushup(x);//建立树的时候,从下往上依次pushup
	}
	void init(int n)
	{
		cnt=0;
		ch[0][0]=ch[0][1]=fa[0]=sz[0]=num[0][0]=num[0][1]=val0[0]=on[0]=val1[0]=gcd0[0]=gcd1[0]=0;//0结点是空节点,代表没有
		//为了方便处理边界,加两个边界顶点
		newNode(root,0,0);
		newNode(ch[root][1],0,0);//这两个边界结点的值不影响正常求解
		fa[cnt]=root;
		sz[root]=2;
		makeTree(KT,1,n,ch[root][1]);
		pushup(ch[root][1]);
		pushup(root);
	}
	int query(int l,int r,int flag)
	{
        rotateto(l-1,0);
        rotateto(r+1,root);
        if(num[KT][flag]==0) return -1;
        return (flag==1?gcd1[KT]:gcd0[KT]);
    }
    void insert(int id,int v,int flag)
    {
        rotateto(id,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        newNode(LC,v,flag);
        fa[LC]=x;
        pushup(x);
        pushup(root);
    }
    void remove(int id)
    {
        rotateto(id-1,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        //fa[LC]=0;
        LC=0;
        pushup(x);
        pushup(root);
    }
    void swap2(int &a,int &b)
    {
        int t=a;a=b;b=t;
    }
    void swap(int x)
    {
        on[x]=1-on[x];
        swap2(val0[x],val1[x]);
        gcd0[x]=gcd(gcd(gcd0[LC],gcd0[RC]),val0[x]);
        gcd1[x]=gcd(gcd(gcd1[LC],gcd1[RC]),val1[x]);
        num[x][0]=num[LC][0]+num[RC][0]+(1-on[x]);
        num[x][1]=num[LC][1]+num[RC][1]+on[x];
    }
    void rev(int id)
    {
        rotateto(id-1,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        swap(KT);
        pushup(x);
        pushup(root);
    }
    void modify(int id,int v)
	{
        rotateto(id-1,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        if(on[LC]==1) val1[LC]=v;
        else val0[LC]=v;
        gcd0[LC]=gcd(gcd(gcd0[ch[LC][0]],gcd0[ch[LC][1]]),val0[LC]);
        gcd1[LC]=gcd(gcd(gcd1[ch[LC][0]],gcd1[ch[LC][1]]),val1[LC]);
        pushup(x);
        pushup(root);
        return;
	}
	void print(int x)
	{
	    if(sz[x]==0) return;
        print(LC);
        printf("on:%d    val0:%d    val1:%d    gcd0:%d   gcd1:%d\n",on[x],val0[x],val1[x],gcd0[x],gcd1[x]);
        print(RC);
	}
	void debug(int x)
	{
        print(x);
        printf("\n");
	}
}spt;
int main()
{
    int i,j;
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++)
            scanf("%d%d",&spt.data[i],&spt.state[i]);
        spt.init(n);
        char com[5];
        int a,b,state;
        while(m--)
        {
            scanf("%s",com);
            if(com[0]=='Q')
            {
                scanf("%d%d%d",&a,&b,&state);
                printf("%d\n",spt.query(a,b,state));
            }
            if(com[0]=='I')
            {
                scanf("%d%d%d",&a,&b,&state);
                spt.insert(a,b,state);
            }
            if(com[0]=='D')
            {
                scanf("%d",&a);
                spt.remove(a);
            }
            if(com[0]=='R')
            {
                scanf("%d",&a);
                spt.rev(a);
            }
            if(com[0]=='M')
            {
                scanf("%d%d",&a,&b);
                spt.modify(a,b);

            }
            //spt.debug(spt.root);
        }
    }
    return 0;
}

zoj 3761 Easy billiards dfs树

这题如果想到的话,写起来很简单。。
题意:无限大的二维坐标系中有n(0<=n<=2000)个球,可以用一个球沿与x坐标轴或y坐标轴平行的方向打球,如果球A碰到球B,那么球A停在球B的地方,球B以与A相同的方向前进,如果B运动的方向前方没有球了,那么判定球B出局,否则球B会撞到球C,以此类推,但是一个球不能直接出局,它必须是被某个球撞击后出局。
思路:把“相邻的球”(即可以直接撞击的球)连边,可以发现,同一个连通快中的球最后只会剩一个,,所以建图后dfs之,形成dfs树,为了保证一个连通块中的点撞到只剩一个,所以只要从子节点撞向父节点即可(比如,(0,0)、(1,0)、(0,1)三个点,dfs之后(0,0)是父节点,另两个是子节点,如果这时从(0,0)撞向(1,0)或(0,1)就会出错)
代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef struct Edge{
    int to;
    int next;
}Edge;
typedef struct Point{
    int x,y;
    int num;
}Point;
Point p[2010];
Edge edge[8000+10];
int head[2010],cnt;
int x[2010],y[2010];
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
int ansx[2010],ansy[2010];
char dir[2010][10];
int num;
bool visit[2010];
void dfs(int cur)
{
    visit[cur]=1;
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(visit[v]) continue;
        dfs(v);
        ansx[++num]=x[v],ansy[num]=y[v];
        if(x[v]==x[cur])
        {
            if(y[v]>y[cur]) strcpy(dir[num],"DOWN");
            else strcpy(dir[num],"UP");
        }
        else if(y[v]==y[cur])
        {
            if(x[v]>x[cur]) strcpy(dir[num],"LEFT");
            else strcpy(dir[num],"RIGHT");
        }
    }
    return;
}
bool cmp1(Point a,Point b)
{
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
bool cmp2(Point a,Point b)
{
    if(a.y!=b.y) return a.y<b.y;
    return a.x<b.x;
}
int main()
{
    int i,j;
    int n;
    while(~scanf("%d",&n))
    {
        num=cnt=0;
        memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&x[i],&y[i]);
            p[i].x=x[i];p[i].y=y[i];p[i].num=i;
        }
        sort(p+1,p+1+n,cmp1);
        for(i=2;i<=n;i++)
        {
            if(p[i].x==p[i-1].x) add(p[i-1].num,p[i].num);
        }
        sort(p+1,p+1+n,cmp2);
        for(i=2;i<=n;i++)
        {
            if(p[i].y==p[i-1].y) add(p[i-1].num,p[i].num);
        }
        memset(visit,0,sizeof(visit));
        for(i=1;i<=n;i++)
        {
            if(visit[i]) continue;
            dfs(i);
        }
        printf("%d\n",n-num);
        for(i=1;i<=num;i++) printf("(%d, %d) %s\n",ansx[i],ansy[i],dir[i]);
    }
    return 0;
}

hdoj1540 Tunnel Warfare

做了一些区间合并,现在已经比较理解了,关键一点是要知道,任何一个连续区,不断向下,一定会被分隔开。
这道题的query,要求包含节点x的1的连续长度。如果m+1-rmax[lson]<=pos && pos<=m+lmax[rson]那么直接返回这一段,否则x所在的连续1区间必定在左子区间或右子区间,继续往下找即可。

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=5e4;
int lmax[maxn<<2],rmax[maxn<<2],mmax[maxn<<2];
int st[maxn+10],top;
inline int max(int a,int b){return a>b?a:b;}
void pushup(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	mmax[id]=max(mmax[lson],mmax[rson]);
	mmax[id]=max(mmax[id],rmax[lson]+lmax[rson]);
	lmax[id]=lmax[lson];
	rmax[id]=rmax[rson];
	if(lmax[lson]==lenl) lmax[id]+=lmax[rson];
	if(rmax[rson]==lenr) rmax[id]+=rmax[lson];
	return;
}
void build(int id,int l,int r)
{
	lmax[id]=rmax[id]=mmax[id]=r-l+1;
	if(l==r) return;
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	return;
}
void update(int id,int l,int r,int pos,int v)
{
	if(l==r)
	{
		lmax[id]=rmax[id]=mmax[id]=v;
		return;
	}
	int m=(l+r)/2;
	if(pos<=m) update(lson,l,m,pos,v);
	else update(rson,m+1,r,pos,v);
	pushup(id,l,r);
	return;
}
int query(int id,int l,int r,int pos)
{
	if(l==r) return mmax[id];
	int m=(l+r)/2;
	if(m+1-rmax[lson]<=pos && pos<=m+lmax[rson]) return rmax[lson]+lmax[rson];
	if(pos<=m) return query(lson,l,m,pos);
	else return query(rson,m+1,r,pos);
}
int main()
{
	int i,j;
	int n,m;
	char com[5];
	int x;
	while(~scanf("%d%d",&n,&m))
	{
		top=0;
		build(1,1,n);
		for(i=1;i<=m;i++)
		{
			scanf("%s",com);
			if(com[0]!=’R') scanf("%d",&x);
			else
			{
				if(!top) continue;
				update(1,1,n,st[top--],1);
			}
			if(com[0]==’D') update(1,1,n,x,0),st[++top]=x;
			if(com[0]==’Q') printf("%d\n",query(1,1,n,x));
		}
	}
	return 0;
}

hdoj2871 Memory Control

这题前面部分和hotel那题是差不多的,也是寻找最左边连续的空白,成段更新,但是free时要输出free掉的起始点和结束点,get操作要输出第x个block的起始位置,这就比较烦了。开始用set,发现不行,因为要求kth并删除,我去,,难道要写splay。。这样代码也太长了吧。、果断谷歌之,发现是用vector解决的,vector可以在制定迭代器之前的位置插入元素,但是这样效率是o(n)吧。。。要是有5e4个查询是get x的话,岂不是效率超低?
解决两个问题:
(1)怎样知道unit x是属于哪个block的,可以维护一个域block[],当区间由多个内存块组成时block[id]=-1,block[id]=0表示id区间没有内存块覆盖。
(2)怎样get第x个(block是按起始点排序的)内存块的起始位置,按起始点维护一个vector。如上所述,插入和删除时先二分找到位置。
insert(iter,element);表示在迭代器iter的前面一个位置插入元素element。
这题比较考验耐心。。

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
using namespace std;
const int maxn=5e4;
int block[maxn<<2],lmax[maxn<<2],rmax[maxn<<2],mmax[maxn<<2];
bool sett[maxn<<2],resett[maxn<<2];
typedef struct Node{
	int begin,len;
	bool operator <(const Node &a) const
	{
		return begin<a.begin;
	}
}Node;
Node mem[maxn+10];
vector<Node> hash;
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
void do_sett(int id,int l,int r,int type)
{
	mmax[id]=lmax[id]=rmax[id]=0;
	block[id]=type;
	sett[id]=1;resett[id]=0;
}
void do_resett(int id,int l,int r)
{
	mmax[id]=lmax[id]=rmax[id]=r-l+1;
	block[id]=0;
	resett[id]=1;sett[id]=0;
}
void pushup(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	if(block[lson]!=block[rson]) block[id]=-1;
	else block[id]=block[lson];
	mmax[id]=max(mmax[lson],mmax[rson]);
	mmax[id]=max(mmax[id],rmax[lson]+lmax[rson]);
	lmax[id]=lmax[lson];
	rmax[id]=rmax[rson];
	if(lmax[lson]==lenl) lmax[id]+=lmax[rson];
	if(rmax[rson]==lenr) rmax[id]+=rmax[lson];
	return;
}
void pushdown(int id,int l,int r)
{
	int m=(l+r)/2;
	if(sett[id]) {do_sett(lson,l,m,block[id]);do_sett(rson,m+1,r,block[id]);sett[id]=0;}
	if(resett[id]) {do_resett(lson,l,m);do_resett(rson,m+1,r);resett[id]=0;}
}
void build(int id,int l,int r)
{
	sett[id]=resett[id]=0;
	lmax[id]=rmax[id]=mmax[id]=r-l+1;
	block[id]=0;
	if(l==r) return;
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	return;
}
void update_sett(int id,int l,int r,int L,int R,int type)
{
	if(L<=l && r<=R)
	{
		do_sett(id,l,r,type);
		return;
	}
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(L<=m) update_sett(lson,l,m,L,R,type);
	if(R>m) update_sett(rson,m+1,r,L,R,type);
	pushup(id,l,r);
	return;
}
void update_resett(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R)
	{
		do_resett(id,l,r);
		return;
	}
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(L<=m) update_resett(lson,l,m,L,R);
	if(R>m) update_resett(rson,m+1,r,L,R);
	pushup(id,l,r);
	return;
}
int query(int id,int l,int r,int len)
{
	if(mmax[id]<len) return 0;
	if(l==r) return l;
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(mmax[lson]>=len) return query(lson,l,m,len);
	if(rmax[lson]+lmax[rson]>=len) return m+1-rmax[lson];
	return query(rson,m+1,r,len);
}
int query_block(int id,int l,int r,int pos)
{
	if(l==r) return block[id];
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(pos<=m) return query_block(lson,l,m,pos);
	else return query_block(rson,m+1,r,pos);
}
int main()
{
	//freopen("data.in","r",stdin);
	int i,j;
	int n,m;
	char com[10];
	int x;
	vector<Node>::iterator it;
	while(~scanf("%d%d",&n,&m))
	{
		int cc=0;
		if(!hash.empty()) hash.clear();
		build(1,1,n);
		for(i=1;i<=m;i++)
		{
			scanf("%s",com);
			if(com[0]!='R') scanf("%d",&x);
			else
			{
				update_resett(1,1,n,1,n);
				printf("Reset Now\n");
				if(!hash.empty()) hash.clear();
			}
			if(com[0]=='N')
			{
				int pos=query(1,1,n,x);
				if(pos)
				{
					cc++;
					mem[cc].begin=pos;mem[cc].len=x;
					it=lower_bound(hash.begin(),hash.end(),mem[cc]);
					hash.insert(it,mem[cc]);
					printf("New at %d\n",pos);
					update_sett(1,1,n,pos,pos+x-1,cc);

				}
				else printf("Reject New\n");
			}
			if(com[0]=='F')
			{
				int ret=query_block(1,1,n,x);
				if(ret==0) printf("Reject Free\n");
				else
				{
					printf("Free from %d to %d\n",mem[ret].begin,mem[ret].begin+mem[ret].len-1);
					update_resett(1,1,n,mem[ret].begin,mem[ret].begin+mem[ret].len-1);
					it=lower_bound(hash.begin(),hash.end(),mem[ret]);
					hash.erase(it);
				}
			}
			if(com[0]=='G')
			{
				if(x>hash.size()) printf("Reject Get\n");
				else printf("Get at %d\n",hash[x-1].begin);
			}
		}
		printf("\n");
	}
	return 0;
}

hdoj3397 Sequence operation

和前面差不多的区间合并,只不多操作多一些,要同时记录1和0的情况

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=5e5;

inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline void swap(int &a,int &b){a^=b;b^=a;a^=b;return;}

int sum[maxn<<2],lmax[maxn<<2],rmax[maxn<<2],mmax[maxn<<2];
int zmmax[maxn<<2],zlmax[maxn<<2],zrmax[maxn<<2];
bool set[maxn<<2],reset[maxn<<2],rev[maxn<<2];

void do_set(int id,int l,int r)
{
	sum[id]=lmax[id]=rmax[id]=mmax[id]=r-l+1;
	zmmax[id]=zlmax[id]=zrmax[id]=0;
	set[id]=1;reset[id]=rev[id]=0;
	return;
}
void do_reset(int id,int l,int r)
{
	sum[id]=lmax[id]=rmax[id]=mmax[id]=0;
	zmmax[id]=zlmax[id]=zrmax[id]=r-l+1;
	reset[id]=1;set[id]=rev[id]=0;
}
void do_rev(int id,int l,int r)
{
	if(set[id]) {do_reset(id,l,r);return;}
	if(reset[id]) {do_set(id,l,r);return;}
	rev[id]^=1;
	sum[id]=r-l+1-sum[id];
	swap(mmax[id],zmmax[id]);
	swap(lmax[id],zlmax[id]);
	swap(rmax[id],zrmax[id]);
	return;
}
void opt(int id,int l,int r,int type)
{
	if(type==0) do_reset(id,l,r);
	if(type==1) do_set(id,l,r);
	if(type==2) do_rev(id,l,r);
	return;
}
void pushup(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	
	sum[id]=sum[lson]+sum[rson];
	
	mmax[id]=max(mmax[lson],mmax[rson]);
	mmax[id]=max(mmax[id],rmax[lson]+lmax[rson]);
	lmax[id]=lmax[lson];
	rmax[id]=rmax[rson];
	if(lmax[lson]==lenl) lmax[id]+=lmax[rson];
	if(rmax[rson]==lenr) rmax[id]+=rmax[lson];

	zmmax[id]=max(zmmax[lson],zmmax[rson]);
	zmmax[id]=max(zmmax[id],zrmax[lson]+zlmax[rson]);
	zlmax[id]=zlmax[lson];
	zrmax[id]=zrmax[rson];
	if(zlmax[lson]==lenl) zlmax[id]+=zlmax[rson];
	if(zrmax[rson]==lenr) zrmax[id]+=zrmax[lson];
	return;
}
void pushdown(int id,int l,int r)
{
    int m=(l+r)/2;
	if(set[id]){do_set(lson,l,m);do_set(rson,m+1,r);set[id]=0;}
	if(reset[id]){do_reset(lson,l,m);do_reset(rson,m+1,r);reset[id]=0;}
	if(rev[id]){do_rev(lson,l,m);do_rev(rson,m+1,r);rev[id]=0;}
	return;
}
void build(int id,int l,int r)
{
	set[id]=reset[id]=rev[id]=0;
	if(l==r)
	{
		scanf("%d",&sum[id]);
		lmax[id]=rmax[id]=mmax[id]=sum[id];
		zmmax[id]=zlmax[id]=zrmax[id]=1-sum[id];
		return;
	}
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	pushup(id,l,r);
	return;
}
void update(int id,int l,int r,int L,int R,int type)
{
	if(L<=l && r<=R)
	{
		opt(id,l,r,type);
		return;
	}
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(L<=m) update(lson,l,m,L,R,type);
	if(R>m) update(rson,m+1,r,L,R,type);
	pushup(id,l,r);
	return;
}
int query_sum(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R) return sum[id];
	pushdown(id,l,r);
	int m=(l+r)/2,ret=0;
	if(L<=m) ret+=query_sum(lson,l,m,L,R);
	if(R>m) ret+=query_sum(rson,m+1,r,L,R);
	return ret;
}
int query_len(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R) return mmax[id];
	pushdown(id,l,r);
	int m=(l+r)/2,ret=0;
	if(L<=m) ret=max(ret,query_len(lson,l,m,L,R));
	if(R>m) ret=max(ret,query_len(rson,m+1,r,L,R));
	ret=max(ret,min(R,m+lmax[rson])-max(L,m+1-rmax[lson])+1);
	return ret;
}
int main()
{
	int i,j,t;
	int n,m;
	int op,a,b;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		build(1,1,n);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&op,&a,&b);a++;b++;
			if(op<=2) update(1,1,n,a,b,op);
			if(op==3) printf("%d\n",query_sum(1,1,n,a,b));
			if(op==4) printf("%d\n",query_len(1,1,n,a,b));
		}
	}
	return 0;
}

hdoj3308 LCIS

单点修改的最长连续递增子序列
比前面几题都要简单,但是磨蹭了n久。。原因是query的时候没弄清楚,query的时候可能去左子区间也可能去右子区间,还有一种是答案是左右子区间拼起来的,想是想到了,但是还是写错了。。这种情况下应该是左起点选max(L,m+1-rmax[lson]),右起点选min(R,m+lmax[rson]).但是我原来写的时候只有当L<=m+1-rmax[lson] && m+lmax[rson]<=R的时候才考虑这种情况。。。

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
#define maxn 100000
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int data[maxn+10];
int lmax[maxn<<2],rmax[maxn<<2],mmax[maxn<<2];
void pushup(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	mmax[id]=max(mmax[lson],mmax[rson]);
	if(data[m]<data[m+1]) mmax[id]=max(mmax[id],rmax[lson]+lmax[rson]);
	lmax[id]=lmax[lson];
	rmax[id]=rmax[rson];
	if(lmax[lson]==lenl && data[m]<data[m+1]) lmax[id]=lenl+lmax[rson];
	if(rmax[rson]==lenr && data[m]<data[m+1]) rmax[id]=lenr+rmax[lson];
	return;
}
void build(int id,int l,int r)
{
	if(l==r)
	{
		lmax[id]=rmax[id]=mmax[id]=1;
		scanf("%d",&data[l]);
		return;
	}
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	pushup(id,l,r);
	return;
}
void update(int id,int l,int r,int pos,int v)
{
	if(l==r)
	{
		data[l]=v;return;
	}
	int m=(l+r)/2;
	if(pos<=m) update(lson,l,m,pos,v);
	else update(rson,m+1,r,pos,v);
	pushup(id,l,r);
	return;
}
int query(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R) return mmax[id];
	int m=(l+r)/2,ret=0;
	if(L<=m) ret=query(lson,l,m,L,R);
	if(R>m) ret=max(ret,query(rson,m+1,r,L,R));
	if(data[m]<data[m+1])
		ret=max(ret,min(m+lmax[rson],R)-max(m+1-rmax[lson],L)+1);
    return ret;
}
void debug(int id,int l,int r)
{
    printf("l:%d  r:%d  mmax:%d\n",l,r,mmax[id]);
    if(l==r) return;
    int m=(l+r)/2;
    debug(lson,l,m);
    debug(rson,m+1,r);
    return;
}
int main()
{
    //freopen("data.in","r",stdin);
	int i,j,t;
	int n,m;
	int a,b;
	char com[3];
	scanf("%d",&t);
	while(t–)
	{
		scanf("%d%d",&n,&m);
		build(1,0,n-1);
		for(i=1;i<=m;i++)
		{
			scanf("%s%d%d",com,&a,&b);
			if(com[0]==’U') update(1,0,n-1,a,b);
			else printf("%d\n",query(1,0,n-1,a,b));
		}
	}
	return 0;
}

poj3667 Hotel

经典的区间合并的线段树
关于找满足要求长度的最左连续空闲区:
维护左起连续空闲区lmax,右起连续空闲区rmax,区间最长连续空闲区max。当区间max=len,若是则转入左子区间,否则看rmax[lson]+lmax[rson]是否>=len,若是,则直接返回m+1-rmax[lson],若还是不行,则忘右区间找一定能找到(因为已经确定max[id]>=len)。
为什么这样是正确的?
如果最终答案不是lmax那段,也不是rmax那段,而是当前区间中间的一段空白,那么如果它被两个子区间隔开,那么必然是rmax[lson]+lmax[rson],否则它必定在左子区间或右子区间,这种情况下会继续往下找。知道所求区间是lmax或rmax或rmax[lson]+lmax[rson]或到达叶子结点。所以只设置这些量是足够的。

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=50000;
int lmax[maxn<<2],max[maxn<<2],rmax[maxn<<2];
bool set[maxn<<2],reset[maxn<<2];
int maxlen(int a,int b,int c)
{
	int ret=a;
	if(b>ret) ret=b;
	if(c>ret) ret=c;
	return ret;
}
void do_set(int id,int l,int r)
{
	lmax[id]=rmax[id]=max[id]=0;
	set[id]=1;reset[id]=0;
	return;
}
void do_reset(int id,int l,int r)
{
	int len=r-l+1;
	lmax[id]=rmax[id]=max[id]=len;
	reset[id]=1;set[id]=0;
	return;
}
void pushup(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	lmax[id]=lmax[lson];
	rmax[id]=rmax[rson];
	if(lmax[lson]==lenl) lmax[id]=lenl+lmax[rson];
	if(rmax[rson]==lenr) rmax[id]=lenr+rmax[lson];
	max[id]=maxlen(lmax[id],rmax[id],rmax[lson]+lmax[rson]);
	max[id]=maxlen(max[id],max[lson],max[rson]);
	return;
}
void pushdown(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	if(reset[id])
	{
		lmax[lson]=rmax[lson]=max[lson]=lenl;reset[lson]=1;set[lson]=0;
		lmax[rson]=rmax[rson]=max[rson]=lenr;reset[rson]=1;set[rson]=0;
		reset[id]=0;
	}
	if(set[id])
	{
		lmax[lson]=rmax[lson]=max[lson]=0;set[lson]=1;reset[lson]=0;
		lmax[rson]=rmax[rson]=max[rson]=0;set[rson]=1;reset[rson]=0;
		set[id]=0;
	}
	return;
}
void build(int id,int l,int r)
{
	set[id]=reset[id]=0;
	lmax[id]=rmax[id]=max[id]=r-l+1;
	if(l==r) return;
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	return;
}
void update(int id,int l,int r,int L,int R,int type)
{
	if(L<=l && r<=R)
	{
		if(type==0) do_reset(id,l,r);
		else do_set(id,l,r);
		return;
	}
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(L<=m) update(lson,l,m,L,R,type);
	if(R>m) update(rson,m+1,r,L,R,type);
	pushup(id,l,r);
	return;
}
int query(int id,int l,int r,int len)
{
	if(max[id]<len) return 0;
	if(l==r) return l;
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(max[lson]>=len) return query(lson,l,m,len);
	if(rmax[lson]+lmax[rson]>=len) return m+1-rmax[lson];
	return query(rson,m+1,r,len);
}
void debug(int id,int l,int r)
{
	if(l==r)
	{
		printf("%d ",1-max[id]);return;
	}
	pushdown(id,l,r);
	int m=(l+r)/2;
	debug(lson,l,m);
	debug(rson,m+1,r);

}
int main()
{
	int i,j;
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		build(1,1,n);
		for(i=1;i<=m;i++)
		{
			int c,a,b;
			scanf("%d",&c);
			if(c==1)
			{
				scanf("%d",&a);
				int pos=query(1,1,n,a);
				if(pos) update(1,1,n,pos,pos+a-1,1);
				printf("%d\n",pos);
				//debug(1,1,n);printf("\n");
				//printf("max[1]:%d\n",max[1]);
			}
			else
			{
				scanf("%d%d",&a,&b);
				update(1,1,n,a,a+b-1,0);
				//debug(1,1,n);printf("\n");
			}
		}
	}
	return 0;
}

poj2991 Crane——线段转化成向量,向量旋转

神奇的一道题,解法很奇妙————对我而言。。
题意:给出一些线段,起始时它们一次邻接的排列在二维笛卡尔坐标系上,端点分别是(0,w1)(0,w1+w2)……(0,w1+w1+……+wn),wi是第i个线段的长度。给出一些操作s,angle。表示把第s条线段的右端点p的后面的所有线段以p为中心旋转到p点两侧的线段成angle角度。(angle角度=以线段s以p点为中心逆时针转到与线段s+1重合经过的角度),要求每次操作后输出线段n右端点的坐标。
难点:直接做很麻烦,因为每次旋转的中心点可能不同,操作无法统一化表示,如果能统一化的话,就可以使用线段树了。
关键点:
1.把线段看成向量。
2.当进行操作是s,angle后,第s+1条线段开始的线段所在直线都旋转了angle角度。
3.向量(x1,y2)逆时针旋转a弧度后的端点坐标为
x1=x0*cos(a)-y0*sin(a);
y1=x0*sin(a)+y0*cos(a);
当顺时针旋转b弧度时,a=-b。相当与旋转了负角度。

有了这三个认识,题目就简单了。线段树中的结点(id,l,r)存储的是第l条线段的右端点到第r条线段的右端点表示的向量的右端点的横纵坐标。所以其实答案就是(x[1],y[1])。
那么怎样把题目告诉的旋转到成angle角度转化为旋转了多少角度呢?
这个简单,只要开个数组angle[],angle[i]表示第i条和第i+1条线段现在所成的角度。那么假如现在要旋转到成r弧度角,那么旋转了r-angle[i].注意化成弧度计算哦。

#include<stdio.h>
#include<string.h>
#include<math.h>
#define lson id<<1
#define rson id<<1|1
#define maxn 10000
const double eps=1e-8;
const double pi=acos((double)(-1.0));
double len[maxn+10],angle[maxn+10];
double x[maxn<<2],y[maxn<<2],rotate[maxn<<2];
double radio(double ang){return (ang*pi)/180;}
void change(double &x,double &y,double ang)
{
	double xx=x,yy=y;
	x=xx*cos(ang)-yy*sin(ang);
	y=xx*sin(ang)+yy*cos(ang);
	return;
}
void pushup(int id)
{
	x[id]=x[lson]+x[rson];
	y[id]=y[lson]+y[rson];
	return;
}
void pushdown(int id)
{
	if(fabs(rotate[id]-0)<eps) return;
	change(x[lson],y[lson],rotate[id]);rotate[lson]+=rotate[id];
	change(x[rson],y[rson],rotate[id]);rotate[rson]+=rotate[id];
	rotate[id]=0;
	return;
}
void build(int id,int l,int r)
{
	rotate[id]=0;
	if(l==r)
	{
		x[id]=0;y[id]=len[l];
		return;
	}
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	pushup(id);
	return;
}
void update(int id,int l,int r,int L,int R,double rad)
{
	if(L<=l && r<=R)
	{
		change(x[id],y[id],rad);
		rotate[id]+=rad;
		return;
	}
	pushdown(id);
	int m=(l+r)/2;
	if(L<=m) update(lson,l,m,L,R,rad);
	if(R>m) update(rson,m+1,r,L,R,rad);
	pushup(id);
	return;
}
int main()
{
	int i,j;
	int n,m;
	bool flag=1;
	while(~scanf("%d%d",&n,&m))
	{
		for(i=1;i<=n;i++) scanf("%lf",&len[i]);
		for(i=1;i<=n;i++) angle[i]=pi;
		int s;
		double ang;
		build(1,1,n);
		if(flag) flag=0;
		else printf("\n");
		for(i=1;i<=m;i++)
		{
			scanf("%d%lf",&s,&ang);
			double r=radio(ang)-angle[s];
			update(1,1,n,s+1,n,r);
			angle[s]=radio(ang);
			printf("%.2f %.2f\n",x[1],y[1]);
		}
	}
	return 0;
}

poj1436 Horizontally Visible Segments

终于ac了,不容易啊。。
题意:给出n条垂直的不相交线段,如果两条线段之间可以用一条不穿过其他线段的水平线段连接起来,那么称这两条线段互相可见。如果三条线段间两两可见,那么称这三条线段组成三角形,问总共有多少个三角形。
思路:每条线段的id(将线段按x坐标排序,id从1开始)作为颜色,用线段树维护区间的颜色。每次插入一条线段,就询问这段区间内有哪些颜色(也就是之前插入的哪些线段与当前线段互相可见),之后更新该区间的颜色。起始时整个区间颜色为0,当一段区间内有多种颜色时color设成-1。
注意一点:
| | |
| |
| | |
1 2 3
上图中x坐标=2的两条线段的y坐标分别为(1,2)(3,4),那么显然线段1和3是互相可见的,但是因为在线段树上插入线段3时[1,4]这个区间颜色全是2,所以会会认为线段3与1不是互相可见。这样就造成了漏数。
解决:方法是线段树的每个点乘2.这样x、x+1变成2x、2x+2,中间的2x+1这个点就可以表示区间(x,x+1).

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<set>
#include<vector>
#define lson id<<1
#define rson id<<1|1
using namespace std;
const int maxn=8000*2;
int color[maxn<<2];
bool lazy[maxn<<2];
typedef struct Seg{
	int x,y1,y2;
}Seg;
Seg seg[maxn/2+10];
set<int> s[maxn/2+10];
set<int>::iterator it;
vector<int> map[maxn/2+10];
int cur;
bool cmp(Seg a,Seg b){return a.x<b.x;}
void pushup(int id)
{
	if(color[lson]!=color[rson]) color[id]=-1;
	else color[id]=color[lson];
	return;
}
void pushdown(int id)
{
	if(!lazy[id] || color[id]==-1 || color[id]==0) return;
	lazy[id]=0;
	color[lson]=color[id];lazy[lson]=1;
	color[rson]=color[id];lazy[rson]=1;
	return;
}
void update(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R)
	{
        color[id]=cur;
		lazy[id]=1;
		return;
	}
	pushdown(id);
	int m=(l+r)/2;
	if(L<=m) update(lson,l,m,L,R);
	if(R>m) update(rson,m+1,r,L,R);
	pushup(id);
	return;
}
void query(int id,int l,int r,int L,int R)
{
	if(color[id]==0) return;
	if(L<=l && r<=R && color[id]!=-1)
	{
		s[cur].insert(color[id]);
		return;
	}
	pushdown(id);
	int m=(l+r)/2;
	if(L<=m) query(lson,l,m,L,R);
	if(R>m) query(rson,m+1,r,L,R);
	return;
}
int main()
{
	int t,n;
	int i,j,k;
	int x,y1,y2;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		int maxd=-1;
		for(i=1;i<=n;i++)
		{
			scanf("%d%d%d",&seg[i].y1,&seg[i].y2,&seg[i].x);
			seg[i].y1*=2;seg[i].y2*=2;
			if(seg[i].y2>maxd) maxd=seg[i].y2;
		}
		sort(seg+1,seg+1+n,cmp);
		for(i=1;i<=n;i++)
		{
			if(!s[i].empty()) s[i].clear();
			if(!map[i].empty()) map[i].clear();
		}
		memset(color,0,sizeof(color));
		memset(lazy,0,sizeof(lazy));
		for(i=1;i<=n;i++)
		{
			cur=i;
			query(1,0,maxn,seg[i].y1,seg[i].y2);
			update(1,0,maxn,seg[i].y1,seg[i].y2);
		}
		for(i=1;i<=n;i++)
		{
			for(it=s[i].begin();it!=s[i].end();it++)
				map[i].push_back(*it);
		}
		int ans=0;
		for(i=1;i<=n;i++)
		{
			for(j=0;j<map[i].size();j++)
				for(k=j+1;k<map[i].size();k++)
				{
					int a=map[i][j],b=map[i][k];
					if(a>b) {a^=b;b^=a;a^=b;}
					if(s[b].find(a)!=s[b].end()) ans++;
				}
		}
		printf("%d\n",ans);
	}
	return 0;
}

poj3225 Help with Intervals——线段树

开始对于区间乘以2的方法没理解透彻导致错误。
由于涉及开闭区间,所以既要用到点又要用到区间。普通线段树实际上是将区间堪看成离散的点,每次操作都是对点进行操作,对连续的区间则无可奈何。
解决方法:对于数x,x乘2,2x表示点本身,2x+1表示(x,x+1)这段区间。这样问题就解决了。

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=(65535<<1|1);
bool set[4*maxn],reset[4*maxn],rev[4*maxn];
int a[maxn+10];
void do_set(int id) {set[id]=1;reset[id]=rev[id]=0;}
void do_reset(int id) {reset[id]=1;set[id]=rev[id]=0;}
void do_rev(int id)
{
	if(set[id]==1) {do_reset(id);return;}
	if(reset[id]==1) {do_set(id);return;}
	rev[id]^=1;return;
}
void do_it(int id,int type)
{
	if(type==1) do_set(id);
	if(type==2) do_reset(id);
	if(type==3) do_rev(id);
}
void pushdown(int id)
{
	if(set[id]) {do_set(lson);do_set(rson);}
	if(reset[id]) {do_reset(lson);do_reset(rson);}
	if(rev[id]) {do_rev(lson);do_rev(rson);}
	set[id]=reset[id]=rev[id]=0;
}
void update(int id,int l,int r,int L,int R,int type)
{
    if(L>R || L<0) return;
	if(L<=l && r<=R)
	{
		do_it(id,type);return;
	}
	pushdown(id);
	int m=(l+r)/2;
	if(L<=m) update(lson,l,m,L,R,type);
	if(R>m) update(rson,m+1,r,L,R,type);
	return;
}
void out(int id,int l,int r)
{
	if(l==r)
	{
		if(set[id] || rev[id]) {a[l]=1;return;}
		if(reset[id]) {a[l]=0;return;}
		a[l]=0;return;
	}
	pushdown(id);
	int m=(l+r)/2;
	out(lson,l,m);
	out(rson,m+1,r);
}
int main()
{
	int i,j;
	char com[5],left,right;
	int l,r;
	memset(set,0,sizeof(set));
	memset(reset,0,sizeof(reset));
	memset(rev,0,sizeof(rev));
	while(~scanf("%s %c%d,%d%c",com,&left,&l,&r,&right))
	{
	    getchar();
		if(left=='[') l<<=1;
		else l=(l<<1|1);
		if(right==')') r=(r<<1)-1;
		else r=(r<<1);
		if(com[0]=='U') update(1,0,maxn,l,r,1);
		if(com[0]=='I') {update(1,0,maxn,0,l-1,2);update(1,0,maxn,r+1,maxn,2);}
		if(com[0]=='D') update(1,0,maxn,l,r,2);
		if(com[0]=='C') {update(1,0,maxn,0,l-1,2);update(1,0,maxn,r+1,maxn,2);update(1,0,maxn,l,r,3);}
		if(com[0]=='S') update(1,0,maxn,l,r,3);
	}
	out(1,0,maxn);
	bool flag=1;
	for(i=0;i<=maxn;i++)
	{
		if(((a[i]==1) && (i==0)) || ((a[i]==1) && (a[i-1]==0)))
		{
			if(!flag) printf(" ");
			else flag=0;
			if(i&1) printf("(%d,",i/2);
			else printf("[%d,",i/2);
		}
		if(((a[i]==1) && (i==maxn)) || ((a[i]==1) && (a[i+1]==0)))
		{
			if(i&1) printf("%d)",i/2+1);
			else printf("%d]",i/2);
		}
	}
	if(flag) printf("empty set");
	printf("\n");
	return 0;
}

hdoj3874 Necklace——线段树离线处理

好久没做题,刷下存在感。。
线段树题,问[l,r]之间数的和,同样的数只算一遍。
思路:把询问离线保存下来,按右端点排序,用hash[x]表示数x到目前为止出现的最右位置。如果x以前出现过,则把位置hash[x]处清零,然后当前位置置为x。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
#define maxn 50000+10
using namespace std;
typedef __int64 ll;
int n,m;
ll sum[4*maxn],ans[200000+10];
typedef struct Q{
	int l,r;
	int num;
}Q;
Q q[200000+10];
int hash[1000000+10];
void pushup(int id)
{
	sum[id]=sum[lson]+sum[rson];
	return;
}
void update(int id,int l,int r,int pos,ll v)
{
	if(l==r)
	{
		sum[id]=v;return;
	}
	int m=(l+r)/2;
	if(pos<=m) update(lson,l,m,pos,v);
	else update(rson,m+1,r,pos,v);
	pushup(id);
	return;
}
ll query(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R) return sum[id];
	int m=(l+r)/2;
	ll ret=0;
	if(L<=m) ret+=query(lson,l,m,L,R);
	if(R>m) ret+=query(rson,m+1,r,L,R);
	return ret;
}
bool cmp(Q a,Q b)
{
	return a.r<b.r;
}
bool cmp2(Q a,Q b)
{
	return a.num<b.num;
}
ll a[maxn];
int main()
{
	int i,j,k,t;
	scanf("%d",&t);
	while(t--)
	{
		memset(hash,0,sizeof(hash));
		memset(sum,0,sizeof(ll)*(4*n+5));
		scanf("%d",&n);//scanint(n);
		for(i=1;i<=n;i++) scanf("%I64d",&a[i]);//scanll(a[i]);
		scanf("%d",&m);//scanint(m);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&q[i].l,&q[i].r);//scanint(q[i].l);scanint(q[i].r);
			q[i].num=i;
		}
		sort(q+1,q+1+m,cmp);
		k=0;
		for(i=1;i<=m;i++)
		{
			for(j=k+1;j<=q[i].r;j++)
			{
				if(!hash[a[j]])
				{
					hash[a[j]]=j;
					update(1,1,n,j,a[j]);
				}
				else
				{
					update(1,1,n,hash[a[j]],0);
					hash[a[j]]=j;
					update(1,1,n,j,a[j]);
				}
			}
			k=q[i].r;
			ans[q[i].num]=query(1,1,n,q[i].l,q[i].r);
		}
		for(i=1;i<=m;i++)
			printf("%I64d\n",ans[i]);
	}

	return 0;
}