【模拟8.01】string(线段树)
2024-08-26 05:47:51
因为题中只有a-z，所以区间中大量字母都是重复的，我们不妨利用桶的性质。
开一棵树，里面维护当前区间内的相同元素，若区间内元素不同，则为零
每次升序操作就先查询一遍区间，用桶将每个区间的a-z元素统计出，
然后按照顺序(L-L+tong[1]-1)..........进行区间修改，
注意要有向上修改的updata！！！
因为区间有很多字母相同，修改近似是mlogn*26（26次嘛....）查询mlong(n);
1 #include<iostream>
2 #include<cstdio>
3 #include<string>
4 #include<algorithm>
5 #include<cmath>
6 #include<vector>
7 #include<map>
8 #include<cstring>
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 }
最新文章
- ENode框架Conference案例分析系列之 - 业务简介
- windows主机开启openssl的方法
- Android实例-从照相机或图库获取照片(XE8+小米2)
- cocos2d-x Animation
- 自定义标签体、MVC
- 使用hubuild,mui开发微信app—首页（一）
- 使Tomcat指向指定的JDK目录
- paping使用来测试联通&网站由于tcp协议导致的无法通信问题超时问题
- awk小例子_1_逆序排列
- 常见的页面中两个div自适应等高CSS控制
- Docker安装MySQL数据库
- LOL新版符文 怎么查看队友的符文配置？
- JQ用法
- linux有趣的命令screen
- Find a way HDU - 2612
- [100]tar命令打包(排除目录或文件)
- Cocos2d-x学习笔记（二）AppDelegate类详解
- logback和slf4j的使用之logger使用
- perl学习笔记（一）
- bootstrap中如何使input中的小图标获得点击事件