hdu4339Query(多校四）

http://acm.hdu.edu.cn/showproblem.php?pid=4339

对线段树还是不熟悉吧写起来挺费劲的大体知道怎么写还是老出错一直纠结区间被砍开了怎么找剩余的部分这部分还必须是跟第一部分连着的

后来想到找到第一个区间之后以区间的r+1作为新的查找点继续递归查找

犯了很二的错误建树建小了该是100W 折腾了差不多4小时吧

View Code

  1 #include<stdio.h>
  2 #include<string.h>
  3 struct node
  4 {
  5     int l,r,data;
  6 }s[3000000];
  7 #define N 1000001
  8 char c1[1000003],c2[1000003];
  9 int num[1000003];
 10 int re,k,flag;
 11 void push(int w)
 12 {
 13     s[w].data = s[2*w].data+s[2*w+1].data;
 14 }
 15 void ctree(int l,int r,int w)
 16 {
 17     s[w].l = l;
 18     s[w].r = r;
 19     if(l==r)
 20     {
 21         s[w].data = num[l];
 22         return ;
 23     }
 24     int m = (l+r)/2;
 25     ctree(l,m,2*w);
 26     ctree(m+1, r,2*w+1);
 27     push(w);
 28 }
 29 void add(int p,int w,int da)
 30 {
 31     if(s[w].l==s[w].r)
 32     {
 33         s[w].data = da;
 34         return ;
 35     }
 36     int m = (s[w].l+s[w].r)/2;
 37     if(p>m)
 38         add(p,2*w+1,da);
 39     else
 40         add(p,2*w,da);
 41     push(w);
 42 }
 43 void search(int p,int w)
 44 {
 45     if(p==s[w].l&&s[w].data==s[w].r-s[w].l+1)
 46     {
 47         re += s[w].data;
 48         if(num[s[w].r+1]==0)
 49         return ;
 50         if(s[w].r<k)
 51         search(s[w].r+1,1);
 52         return ;
 53     }
 54     if(s[w].l==s[w].r)
 55     return ;
 56     int m = (s[w].l+s[w].r)/2;
 57     if(p>m)
 58     search(p,2*w+1);
 59     else
 60     search(p,2*w);
 61 }
 62 int main()
 63 {
 64     int i,j,n,m,t,q,a,b,c,o = 0;
 65     char d;
 66     scanf("%d", &t);
 67     while(t--)
 68     {
 69         o++;
 70         getchar();
 71         memset(num,0,sizeof(num));
 72         gets(c1);
 73         gets(c2);
 74         int k1 = strlen(c1);
 75         int k2 = strlen(c2);
 76         if(k1>k2)
 77             k = k2;
 78         else
 79             k = k1;
 80         for(i = 0 ; i < k  ;i++)
 81         {
 82             if(c1[i]!=c2[i])
 83                 num[i+1] = 0;
 84             else
 85                 num[i+1] = 1;
 86         }
 87         ctree(1,N,1);
 88         scanf("%d", &q);
 89         printf("Case %d:\n",o);
 90         while(q--)
 91         {
 92             scanf("%d", &a);
 93             if(a==2)
 94             {
 95                 scanf("%d", &b);
 96                 if(num[b+1]==0)
 97                 {
 98                     printf("0\n");
 99                     continue;
100                 }
101                 re = 0;
102                 search(b+1,1);
103                 printf("%d\n",re);
104             }
105             else
106             {
107                 scanf("%d %d %c", &b,&c,&d);
108                 if(c1[c]==c2[c])
109                 {
110                     if(b==1)
111                     c1[c] = d;
112                     else
113                     c2[c] = d;
114                     if(c1[c]!=c2[c])
115                     {
116                         num[c+1] = 0;
117                         add(c+1,1,-1);
118                     }
119                 }
120                 else
121                 {
122                     if(b==1)
123                     c1[c] = d;
124                     else
125                     c2[c] = d;
126                     if(c1[c]==c2[c])
127                     {
128                         num[c+1] = 1;
129                         add(c+1,1,1);
130                     }
131                 }
132             }
133         }
134     }
135     return 0;
136 }