POJ-3225 Help with Intervals-セグメントツリー/セグメント更新+増倍区間法

标题:0-65535の区間を与えて、区間の端点はLで、R区間は開区間閉区間の分があって、最初はあなたは1つのS区間を持って、全空の区間です
n回の操作は、操作ごとに4種類あり、
U:T区間L,Rを1(S U T)に覆う
I:T区間を求める、SとTが交わる、つまり[-∞,l)(r,∞]を0に覆う
D:原区間Sで与えられた区間Tを減算する、つまり区間Tをゼロにする
C:与えられた区間TでSを減算し、結果をSに付与します.つまり、[-∞,l)(r,∞]を0に上書きし、【l,r】を逆にします
S:異を求めるか、直接区間【l,r】を逆にする
上の操作はすべて線分の木の区間で更新して完成することができて、それぞれ1つのsetの操作で、1つの異を求める操作で、私達は遅延のマークを下ろす時、前後をはっきり区別することに注意して、先にsetの操作を下ろして、しかもsetの操作の後で異あるいはマークをクリアする必要があります.
異或操作の場合、現在のノードにsetタグがある場合は、setタグを逆にするだけでよく、setタグがない場合は逆またはタグをとる
もう一つ重要な問題は開閉区間の問題であり,この問題を倍増区間法で解決する

(l, r) --> [2 * l + 1, 2 * r - 1]
(l, r] --> [2 * l + 1, 2 * r]
[l, r) --> [2 * l, 2 * r - 1]
[l, r] --> [2 * l, 2 *r]

偶数点で整数点を表し、奇数点で2つの整数点の間のすべての非整数点を表すと、問題は解決する.
端点を直接2に乗じ、左に開くとl++、右に開くとr--、処理後最後に出力される端点がl/2(r+1)/2 lまたはrが奇数の場合、開区間に対応し、逆に閉区間

<span style="font-size:14px;">#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iostream>
using namespace std;
#define ptf(ar1,ar2)  printf("%d:%d
",ar1,ar2);
typedef __int64 ll;
const ll maxn = 131570+500;
int vis[131570+500]; 
struct tree
{
	int  set[maxn*4],yihuo[maxn*4];
	void pd_set(int i,int l,int r)
	{ 
		if (set[i]!=-1)
		{
			set[i<<1]=set[i<<1|1]=set[i]; 
			yihuo[i<<1]=yihuo[i<<1|1]=yihuo[i]=0; 
			set[i]=-1;
		} 
		if (yihuo[i])
		{
			if (set[i<<1]!=-1) set[i<<1]^=1;
			else 	yihuo[i<<1]^=1;
			if (set[i<<1|1]!=-1) set[i<<1|1]^=1;
			else	yihuo[i<<1|1]^=1;
			yihuo[i]=0;  
		}
	}
	void update(int l,int r,int ql,int qr,int i,int val,int op)
	{
		if (ql>r||qr<l) return ;
		if (ql<=l&&qr>=r)
		{ 
			if (op)
			{
				if (set[i]!=-1) set[i]^=1;
				else 	yihuo[i]^=1; 
			}
			else
			{
				set[i]=val; 
				yihuo[i]=0;
			}
			return ;
		}
		pd_set(i,l,r); 
		int m=(l+r)>>1;
		update(l,m,ql,qr,i<<1,val,op);
		update(m+1,r,ql,qr,i<<1|1,val,op); 
	} 
	void init()
	{
		//	memset(sum,0,sizeof(sum));
		//	memset(yihuo,0,sizeof(yihuo));
		//	memset(set,-1,sizeof(set));
	}
	int query2( int l,int r,int i)
	{ 
		if  (l==r)
		{
			if (set[i]==1) vis[r]=1;
			return 0;
		}
		pd_set(i,l,r);
		int mid=(l+r)>>1;
		query2(l,mid,i<<1); 
		query2(mid+1,r,i<<1|1);
	}
	
};

tree tp ;
int main(  )
{
    char op;
    int l,r;
    char lrat,rrat;
    tp.init();
	while(scanf("%c %c%d,%d%c",&op,&lrat,&l,&r,&rrat)!=EOF)
    {
		getchar();
        l*=2;
        r*=2;
        if (lrat=='(') l++;
        if (rrat==')') r--;
        if (op=='U')
            tp.update(0,131570,l,r,1,1,0);
        if (op=='I') 
        {
            tp.update(0,131570,0,l-1,1,0,0);
            tp.update(0,131570,r+1,131570,1,0,0);
        }
        if (op=='D')
            tp.update(0,131570,l,r,1,0,0);
        if (op=='C')
        {
            tp.update(0,131570,0,l-1,1,0,0);
            tp.update(0,131570,r+1,131570,1,0,0);
            tp.update(0,131570,l,r,1,1,1);
			
        }
        if (op=='S')
            tp.update(0,131570,l,r,1,1,1);
		
    }
	int i;
	tp.query2(0,131570 ,1);
	
    int line=0;
    int exist=0;
    for(  i=0; i<=131570 ; i++)
    {
		
        if (vis[i])
        {
            exist=1;
            if (line)  printf(" ");
            int j=i+1;
            while(vis[j]&&j<=131570) j++;
            j--;
            if (i%2) printf("(");
            else printf("[");
			
            printf("%d,%d",i/2,(j+1)/2);
            if (j%2)
                printf(")");
            else
                printf("]");
            line=1;
            i=j;
        }
    }
	if (exist==0)
		printf("empty set");
	
	printf("
");
	return 0;
}
</span>