【模拟8.01】string(线段树)

V2AS问路

【模拟8.01】string(线段树)

阅读原文时间：2023年07月08日阅读：1

因为题中只有a-z，所以区间中大量字母都是重复的，我们不妨利用桶的性质。

开一棵树，里面维护当前区间内的相同元素，若区间内元素不同，则为零

每次升序操作就先查询一遍区间，用桶将每个区间的a-z元素统计出，

然后按照顺序(L-L+tong[1]-1)……….进行区间修改，

注意要有向上修改的updata！！！

因为区间有很多字母相同，修改近似是mlogn*26（26次嘛….）查询mlong(n);

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #define ll long long
10 #define MAXN 510000
11 using namespace std;
12 int read()
13 {
14 int x=0;char cc=getchar();
15 while(cc<'0'||cc>'9'){cc=getchar();}
16 while(cc>='0'&&cc<='9'){x=(x<<1)+(x<<3)+(cc^48);cc=getchar();} 17 return x; 18 } 19 char s[MAXN]; 20 int tong[MAXN];int n,m; 21 struct node{int l,r,me;}T[MAXN*4]; 22 void build(int k,int l,int r) 23 { 24 T[k].l=l;T[k].r=r; 25 //printf("l=%d r=%d\n",l,r); 26 if(l==r) 27 { 28 T[k].me=s[l]-'a'+1; 29 return ; 30 } 31 int mid=(l+r)>>1;
32 build(k<<1,l,mid); 33 build((k<<1)|1,mid+1,r); 34 if(T[(k<<1)].me==T[(k<<1)|1].me) 35 { 36 T[k].me=T[(k<<1)].me; 37 } 38 } 39 void pushdown(int k) 40 { 41 T[k<<1].me=T[k].me; 42 T[(k<<1)|1].me=T[k].me; 43 return ; 44 } 45 void updata(int k) 46 { 47 if(T[k<<1].me==T[(k<<1)|1].me) 48 T[k].me=T[k<<1].me; 49 else T[k].me=0; 50 } 51 void query(int k,int l,int r) 52 { 53 //printf("k=%d l=%d r=%d Tl=%d Tr=%d\n",k,l,r,T[k].l,T[k].r); 54 if(l<=T[k].l&&r>=T[k].r&&T[k].me!=0)
55 {
56 tong[T[k].me]+=T[k].r-T[k].l+1;
57 return ;
58 }
59 if(T[k].l==T[k].r)
60 {
61 return ;
62 }
63 if(T[k].me)pushdown(k);
64 int mid=(T[k].l+T[k].r)>>1;
65 if(l<=mid)query(k<<1,l,r); 66 if(r>mid)query((k<<1)|1,l,r); 67 return ; 68 } 69 int find(int k,int l) 70 { 71 if(T[k].l==T[k].r) 72 { 73 // printf("T[k].l=%d T[k].r=%d T[k].me=%d\n",T[k].l,T[k].r,T[k].me); 74 return T[k].me; 75 } 76 if(T[k].me)pushdown(k); 77 int mid=(T[k].l+T[k].r)>>1;
78 if(l<=mid)find(k<<1,l); 79 else find((k<<1)|1,l); 80 } 81 void add(int k,int l,int r,int x) 82 { 83 if(l<=T[k].l&&r>=T[k].r)
84 {
85 T[k].me=x;
86 //printf("xiugai k=%d l=%d r=%d x=%d\n",k,T[k].l,T[k].r,x);
87 return ;
88 }
89 if(T[k].me)pushdown(k);
90 int mid=(T[k].l+T[k].r)>>1;
91 if(l<=mid) add(k<<1,l,r,x); 92 if(r>mid) add((k<<1)|1,l,r,x); 93 updata(k); 94 //printf("---T[k].me=%d\n",T[13].me); 95 return ; 96 } 97 void clear(int k,int l,int r) 98 { 99 if(l<=T[k].l&&r>=T[k].r)
100 {
101 T[k].me=0;
102 }
103 if(T[k].l==T[k].r)return ;
104 int mid=(T[k].l+T[k].r)>>1;
105 if(l<=mid) clear(k<<1,l,r); 106 if(r>mid) clear((k<<1)|1,l,r); 107 return ; 108 } 109 void out() 110 { 111 for(int i=1;i<=n;++i) 112 { 113 putchar(find(1,i)+'a'-1); 114 } 115 printf("\n"); 116 } 117 void work(int l,int r,int orz) 118 { //printf("------\n"); 119 query(1,l,r); 120 //clear(1,l,r); 121 if(orz==1) 122 { 123 int kx=l; 124 for(int i=1;i<=26;++i) 125 { 126 //printf("tong[%d]=%d\n",i,tong[i]); 127 if(kx+tong[i]-1>=kx)
128 {
129 //printf("add=%d i=%d\n",kx,i);
130 add(1,kx,kx+tong[i]-1,i);
131 //out();
132 }
133 kx+=tong[i];
134 }
135 for(int i=1;i<=26;++i)tong[i]=0;
136 }
137 else
138 {
139 int kx=r;
140 for(int i=1;i<=26;++i)
141 {
142 if(kx-tong[i]+1<=kx)
143 {
144 add(1,kx-tong[i]+1,kx,i);
145 }
146 kx-=tong[i];
147 }
148 for(int i=1;i<=26;++i)tong[i]=0;
149 }
150 //out();
151 }
152 int main()
153 {
154 //freopen("text.in","r",stdin);
155 //freopen("wa.out","w",stdout);
156 n=read();m=read();
157 scanf("%s",s+1);
158 build(1,1,n);
159 for(int i=1;i<=m;++i)
160 {
161 int l,r,orz;
162 scanf("%d%d%d",&l,&r,&orz);
163 work(l,r,orz);
164 }
165 for(int i=1;i<=n;++i)
166 {
167 putchar(find(1,i)+'a'-1);
168 }
169 printf("\n");
170 }

手机扫一扫

移动阅读更方便

你可能感兴趣的文章