Crayon 线段树或者树状数组

Crayon

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

Background

Mary love painting so much, but as we know she can't draw very well. There is no one appreciate her works, so she come up with a puzzle with herself.

Description

There are only one case in each input file, the first line is a integer N (N ≤ 1,000,00) denoted the total operations executed by Mary.

Then following N lines, each line is one of the folling operations.

D L R : draw a segment [L, R], 1 ≤ L ≤ R ≤ 1,000,000,000.
C I : clear the ith added segment. It’s guaranteed that the every added segment will be cleared only once.
Q L R : query the number of segment sharing at least a common point with interval [L, R]. 1 ≤ L ≤ R ≤ 1,000,000,000.

Input

Then following n operations ...

Output

For each query, print the result on a single line ...

Sample Input

Sample Output

2
2

线段树

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <math.h>
  4 #include <string.h>
  5 #include <algorithm>
  6 using namespace std;
  7 #define ll long long
  8 typedef struct abcd
  9 {
 10     int l,r,ci,i;
 11     char x;
 12 } abcd;
 13 abcd a[110000];
 14 typedef struct abc
 15 {
 16     int x,i;
 17 } abc;
 18 abc c[300000];
 19 int cn=0,b[110000],bn=1;
 20 bool cmp(abc x,abc y)
 21 {
 22     return x.x<y.x;
 23 }
 24 bool cmp1(abcd x,abcd y)
 25 {
 26     return x.l<y.l;
 27 }
 28 bool cmp2(abcd x,abcd y)
 29 {
 30     return x.r<y.r;
 31 }
 32 bool cmp3(abcd x,abcd y)
 33 {
 34     return x.i<y.i;
 35 }
 36 typedef struct tree
 37 {
 38     int a,d,sub;
 39 } tree;
 40 tree t[600000];
 41 void fun(int x)
 42 {
 43     if(t[x].d)
 44     {
 45         t[x<<1].d+=t[x].d;
 46         t[x<<1].sub+=t[x].d;
 47         t[x<<1|1].sub+=t[x].d;
 48         t[x<<1|1].d+=t[x].d;
 49         t[x<<1].a+=t[x].d;
 50         t[x<<1|1].a+=t[x].d;
 51         t[x].d=0;
 52     }
 53 }
 54 void update(int x,int y,int b,int c,int tt,int z)
 55 {
 56     if(x<=b&&y>=c)
 57     {
 58         t[tt].sub+=z;
 59         t[tt].d+=z;
 60         t[tt].a+=z;
 61         return ;
 62     }
 63     if(t[tt].d)
 64     fun(tt);
 65     int m=(b+c)>>1;
 66     if(x<=m&&y>m)t[tt].sub+=z;
 67     if(x<=m)update(x,y,b,m,tt<<1,z);
 68     if(y>m)update(x,y,m+1,c,tt<<1|1,z);
 69     t[tt].a=t[tt<<1].a+t[tt<<1|1].a-t[tt].sub;
 70 }
 71 int query(int x,int y,int b,int c,int tt)
 72 {
 73     if(x<=b&&y>=c)
 74     {
 75         return t[tt].a;
 76     }
 77     if(t[tt].d)
 78     fun(tt);
 79     int m=(b+c)>>1;
 80     int r=0,sub;
 81     if(x<=m)r=query(x,y,b,m,tt<<1);
 82     if(y>m)r=r+query(x,y,m+1,c,tt<<1|1);
 83     t[tt].a=t[tt<<1].a+t[tt<<1|1].a-t[tt].sub;
 84     if(x<=m&&y>m)
 85         return r-t[tt].sub;
 86     else return r;
 87 }
 88 int main()
 89 {
 90     int n,i,j;
 91    //freopen("in.txt","r",stdin);
 92     scanf("%d",&n);
 93     for(i=0; i<n; i++)
 94     {
 95         getchar();
 96         scanf("%c",&a[i].x);
 97         if(a[i].x=='C')
 98         {
 99             scanf("%d",&a[i].ci);
100         }
101         else
102         {
103             scanf("%d%d",&a[i].l,&a[i].r);
104             c[cn++].x=a[i].l,c[cn++].x=a[i].r;
105             if(a[i].x=='D')
106                 b[bn++]=i;
107         }
108         a[i].i=i;
109     }
110     int now=2;
111     sort(c,c+cn,cmp);
112     c[0].i=1;
113     for(i=1; i<cn; i++)
114     {
115         if(c[i].x==c[i-1].x)
116             c[i].i=c[i-1].i;
117         else c[i].i=now++;
118     }
119 
120     sort(a,a+n,cmp1);
121     j=0;
122     for(i=0; i<n; i++)
123     {
124         while(i<n&&a[i].x=='C')i++;
125         if(i==n)break;
126         while(a[i].l!=c[j].x)j++;
127         a[i].l=c[j].i;
128     }
129     sort(a,a+n,cmp2);
130     j=0;
131     for(i=0; i<n; i++)
132     {
133         while(i<n&&a[i].x=='C')i++;
134         if(i==n)break;
135         while(a[i].r!=c[j].x)j++;
136         a[i].r=c[j].i;
137     }
138     sort(a,a+n,cmp3);
139     /*for(i=0; i<n; i++)
140         cout<<a[i].x<<" "<<a[i].l<<" "<<a[i].r<<endl;*/
141     memset(t,0,sizeof(t));
142     for(i=0; i<n; i++)
143     {
144         if(a[i].x=='D')
145         {
146             update(a[i].l,a[i].r,1,c[cn-1].i,1,1);
147         }
148         else if(a[i].x=='C')
149         {
150             update(a[b[a[i].ci]].l,a[b[a[i].ci]].r,1,c[cn-1].i,1,-1);
151         }
152         else
153         {
154             printf("%d
",query(a[i].l,a[i].r,1,c[cn-1].i,1));
155         }
156     }
157 }

View Code

树状数组

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <math.h>
  4 #include <string.h>
  5 #include <algorithm>
  6 using namespace std;
  7 #define ll long long
  8 typedef struct abcd
  9 {
 10     int l,r,ci,i;
 11     char x;
 12 } abcd;
 13 abcd a[110000];
 14 typedef struct abc
 15 {
 16     int x,i;
 17 } abc;
 18 abc c[300000];
 19 int cn=0,b[110000],bn=1;
 20 bool cmp(abc x,abc y)
 21 {
 22     return x.x<y.x;
 23 }
 24 bool cmp1(abcd x,abcd y)
 25 {
 26     return x.l<y.l;
 27 }
 28 bool cmp2(abcd x,abcd y)
 29 {
 30     return x.r<y.r;
 31 }
 32 bool cmp3(abcd x,abcd y)
 33 {
 34     return x.i<y.i;
 35 }
 36 int ab[800000][2],m;
 37 int lowbit(int x)
 38 {
 39     return x&(-x);
 40 }
 41 void update(int y,int x,int z)
 42 {
 43     while(x<=m)
 44     {
 45         ab[x][y]+=z;
 46         x+=lowbit(x);
 47     }
 48 }
 49 int query(int y,int x)
 50 {
 51     int sum=0;
 52     while(x>0)
 53     {
 54         sum+=ab[x][y];
 55         x-=lowbit(x);
 56     }
 57     return sum;
 58 }
 59 int main()
 60 {
 61     int n,i,j;
 62    // freopen("in.txt","r",stdin);
 63     scanf("%d",&n);
 64     for(i=0; i<n; i++)
 65     {
 66         getchar();
 67         scanf("%c",&a[i].x);
 68         if(a[i].x=='C')
 69         {
 70             scanf("%d",&a[i].ci);
 71         }
 72         else
 73         {
 74             scanf("%d%d",&a[i].l,&a[i].r);
 75             c[cn++].x=a[i].l,c[cn++].x=a[i].r;
 76             if(a[i].x=='D')
 77                 b[bn++]=i;
 78         }
 79         a[i].i=i;
 80     }
 81     int now=2,sum=0;
 82     sort(c,c+cn,cmp);
 83     c[0].i=1;
 84     for(i=1; i<cn; i++)
 85     {
 86         if(c[i].x==c[i-1].x)
 87             c[i].i=c[i-1].i;
 88         else c[i].i=now++;
 89     }
 90 
 91     sort(a,a+n,cmp1);
 92     j=0;
 93     for(i=0; i<n; i++)
 94     {
 95         while(i<n&&a[i].x=='C')i++;
 96         if(i==n)break;
 97         while(a[i].l!=c[j].x)j++;
 98         a[i].l=c[j].i;
 99     }
100     sort(a,a+n,cmp2);
101     j=0;
102     for(i=0; i<n; i++)
103     {
104         while(i<n&&a[i].x=='C')i++;
105         if(i==n)break;
106         while(a[i].r!=c[j].x)j++;
107         a[i].r=c[j].i;
108     }
109     sort(a,a+n,cmp3);
110     /*for(i=0; i<n; i++)
111         cout<<a[i].x<<" "<<a[i].l<<" "<<a[i].r<<endl;*/
112     m=c[cn-1].i;
113     for(i=0; i<n; i++)
114     {
115         if(a[i].x=='D')
116         {
117             update(0,a[i].l,1);
118             update(1,a[i].r,1);
119             sum++;
120         }
121         else if(a[i].x=='C')
122         {
123             update(0,a[b[a[i].ci]].l,-1);
124             update(1,a[b[a[i].ci]].r,-1);
125             sum--;
126         }
127         else
128         {
129             int ans=query(0,a[i].r);
130             ans-=query(1,a[i].l-1);
131             printf("%d
",ans);
132         }
133     }
134 }

View Code