Codeforces Round #590 (Div. 3)

Stella981
• 阅读 576

D. Distinct Characters Queries

Description

You are given a string ss consisting of lowercase Latin letters and qq queries for this string.

Recall that the substring s[l;r]s[l;r] of the string ss is the string slsl+1…srslsl+1…sr. For example, the substrings of "codeforces" are "code", "force", "f", "for", but not "coder" and "top".

There are two types of queries:

  • 1 pos c1 pos c (1≤pos≤|s|1≤pos≤|s|, cc is lowercase Latin letter): replace sposspos with cc (set spos:=cspos:=c);
  • 2 l r2 l r (1≤l≤r≤|s|1≤l≤r≤|s|): calculate the number of distinct characters in the substring s[l;r]s[l;r].

Input

The first line of the input contains one string ss consisting of no more than 105105 lowercase Latin letters.

The second line of the input contains one integer qq (1≤q≤1051≤q≤105) — the number of queries.

The next qq lines contain queries, one per line. Each query is given in the format described in the problem statement. It is guaranteed that there is at least one query of the second type.

output

For each query of the second type print the answer for it — the number of distinct characters in the required substring in this query.

Examples

Input

abacaba
5
2 1 4
1 4 b
1 5 b
2 4 6
2 1 7

Output

3
1
2

正确解法:

原本想着可修改的主席树来着,树状数组加上主席树。

改模板改了好久没过。

操作一:改变某个字符

操作二:统计区间【l,r】不同字符的个数。

26个字母的树状数组:

每次需要for26次,统计这个字母是否在区间内。

Codeforces Round #590 (Div. 3) Codeforces Round #590 (Div. 3)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <algorithm>
 5 #include <set>
 6 #include <queue>
 7 #include <stack>
 8 #include <string>
 9 #include <cstring>
10 #include <vector>
11 #include <map>
12 //#include <unordered_map>
13 #define mem( a ,x ) memset( a , x ,sizeof(a) )
14 #define rep( i ,x ,y ) for( int i = x ; i<=y ;i++ )
15 #define lson  l ,mid ,pos<<1
16 #define rson mid+1 ,r ,pos<<1|1
17 using namespace std;
18 typedef long long ll ;
19 typedef pair<int ,int> pii;
20 typedef pair<ll ,int> pli;
21 const int inf = 0x3f3f3f3f;
22 const int N = 1e5+100;
23 const ll mod =1e9+7 ;
24 char s[N],kkk;
25 int n,m;
26 int aa,bb,cc;
27 int bit[30][N];
28 int bitsize(int x)
29 {
30     return x&(-x);
31 }
32 void update(int k,int id,int x)
33 {
34     while(id<=n)
35     {
36         bit[k][id]+=x;
37         id+=bitsize(id);
38     }
39 }
40 int query(int k,int id)
41 {
42     int ans=0;
43     while(id>0)
44     {
45         ans+=bit[k][id];
46         id-=bitsize(id);
47     }
48     return ans;
49 }
50 int main()
51 {
52     scanf("%s",s+1);
53     n=strlen(s+1);
54     for(int i=1;i<=n;i++)
55     {
56         update(s[i]-'a'+1,i,1);
57     }
58     scanf("%d",&m);
59     while(m--)
60     {
61         scanf("%d",&aa);
62         if(aa==1)
63         {
64             scanf("%d %c",&bb,&kkk);
65             update(s[bb]-'a'+1,bb,-1);
66             s[bb]=kkk;
67             update(s[bb]-'a'+1,bb,1);
68         }
69         else
70         {
71             scanf("%d%d",&bb,&cc);
72             int ans=0,res;
73             for(int i=1;i<=26;i++)
74             {
75                 res=query(i,cc)-query(i,bb-1);
76                 if(res>0)   ans++;
77             }
78             printf("%d\n",ans);
79         }
80     }
81 
82     return 0;
83 }

View Code

Codeforces Round #590 (Div. 3)

26个字母的线段树:

Codeforces Round #590 (Div. 3) Codeforces Round #590 (Div. 3)

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cmath>
  4 #include <algorithm>
  5 #include <set>
  6 #include <queue>
  7 #include <stack>
  8 #include <string>
  9 #include <cstring>
 10 #include <vector>
 11 #include <map>
 12 //#include <unordered_map>
 13 #define mem( a ,x ) memset( a , x ,sizeof(a) )
 14 #define rep( i ,x ,y ) for( int i = x ; i<=y ;i++ )
 15 #define lson  l ,mid ,pos<<1
 16 #define rson mid+1 ,r ,pos<<1|1
 17 using namespace std;
 18 typedef long long ll ;
 19 typedef pair<int ,int> pii;
 20 typedef pair<ll ,int> pli;
 21 const int inf = 0x3f3f3f3f;
 22 const int N = 1e5+100;
 23 const ll mod =1e9+7 ;
 24 char s[N],kkk;
 25 int n,m;
 26 int aa,bb,cc;
 27 int tree[30][4*N],ans[30],a[N];
 28 void push_up(int rt)
 29 {
 30     for(int i=1;i<=26;i++)
 31         tree[i][rt]=tree[i][rt<<1]+tree[i][rt<<1|1];
 32 }
 33 void build(int rt,int l,int r)
 34 {
 35     if(l==r)
 36     {
 37         tree[a[l]][rt]++;
 38         return;
 39     }
 40     int mid=l+r >>1;
 41     build(rt<<1,l,mid);
 42     build(rt<<1|1,mid+1,r);
 43     push_up(rt);
 44 }
 45 void update(int rt,int p,int x,int y,int l,int r)
 46 {
 47     if(l==r)
 48     {
 49         tree[x][rt]--;
 50         tree[y][rt]++;
 51         return;
 52     }
 53     int mid=l+r>>1;
 54     if(p<=mid)
 55         update(rt<<1,p,x,y,l,mid);
 56     else
 57         update(rt<<1|1,p,x,y,mid+1,r);
 58     push_up(rt);
 59 }
 60 void query(int l,int r,int rt,int L,int R)
 61 {
 62     if(r<=R&&L<=l)
 63     {
 64         for(int i=1;i<=26;i++)
 65             ans[i]+=tree[i][rt];
 66         return ;
 67     }
 68     int mid=l+r>>1;
 69     if(L<=mid)  query(l,mid,rt<<1,L,R);
 70     if(R>mid)   query(mid+1,r,rt<<1|1,L,R);
 71 }
 72 int main()
 73 {
 74     scanf("%s",s+1);
 75     n=strlen(s+1);
 76     for(int i=1;i<=n;i++)
 77         a[i]=s[i]-'a'+1;
 78     build(1,1,n);
 79     scanf("%d",&m);
 80     while(m--)
 81     {
 82         scanf("%d",&aa);
 83         if(aa==1)
 84         {
 85             scanf("%d %c",&bb,&kkk);
 86             update(1,bb,s[bb]-'a'+1,kkk-'a'+1,1,n);
 87             s[bb]=kkk;
 88         }
 89         else
 90         {
 91             scanf("%d%d",&bb,&cc);
 92             int sum=0;
 93             memset(ans,0,sizeof(ans));
 94             query(1,n,1,bb,cc);
 95             for(int i=1;i<=26;i++)
 96                 if(ans[i])
 97                     sum++;
 98             printf("%d\n",sum);
 99         }
100     }
101 
102     return 0;
103 }

View Code

 Codeforces Round #590 (Div. 3)

统计每个字母的下标。用set来快速删除加入元素。

Codeforces Round #590 (Div. 3) Codeforces Round #590 (Div. 3)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <algorithm>
 5 #include <set>
 6 #include <queue>
 7 #include <stack>
 8 #include <string>
 9 #include <cstring>
10 #include <vector>
11 #include <map>
12 //#include <unordered_map>
13 #define mem( a ,x ) memset( a , x ,sizeof(a) )
14 #define rep( i ,x ,y ) for( int i = x ; i<=y ;i++ )
15 #define lson  l ,mid ,pos<<1
16 #define rson mid+1 ,r ,pos<<1|1
17 using namespace std;
18 typedef long long ll ;
19 typedef pair<int ,int> pii;
20 typedef pair<ll ,int> pli;
21 const int inf = 0x3f3f3f3f;
22 const int N = 1e5+100;
23 const ll mod =1e9+7 ;
24 char s[N],kkk;
25 int n,m;
26 int aa,bb,cc;
27 set<int>st[30];
28 set<int>::iterator it;
29 int main()
30 {
31     scanf("%s",s+1);
32     n=strlen(s+1);
33     for(int i=1;i<=n;i++)
34         st[s[i]-'a'+1].insert(i);
35     scanf("%d",&m);
36     while(m--)
37     {
38         scanf("%d",&aa);
39         if(aa==1)
40         {
41             scanf("%d %c",&bb,&kkk);
42             st[s[bb]-'a'+1].erase(bb);
43             s[bb]=kkk;
44             st[s[bb]-'a'+1].insert(bb);
45         }
46         else
47         {
48             scanf("%d%d",&bb,&cc);
49             int ans=0;
50             for(int i=1;i<=26;i++)
51             {
52                 it=st[i].lower_bound(bb);
53                 if(it==st[i].end()) continue;
54                 if((*it)<=cc)
55                     ans++;
56             }
57             printf("%d\n",ans);
58         }
59     }
60 
61     return 0;
62 }

View Code

 Codeforces Round #590 (Div. 3)

哦根据状压的思想,把每个字母变成二进制 (1<<x) 判断是否有这个字母就看二进制那个位置上是否为1

判断字母个数就是看二进制上有多少个1。

如果目前没有这个字母,加上就可以了,如果有了,就不变。

| 很好解决了这个问题。

这样一个线段树就完事了。

Codeforces Round #590 (Div. 3) Codeforces Round #590 (Div. 3)

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cmath>
  4 #include <algorithm>
  5 #include <set>
  6 #include <queue>
  7 #include <stack>
  8 #include <string>
  9 #include <cstring>
 10 #include <vector>
 11 #include <map>
 12 //#include <unordered_map>
 13 #define mem( a ,x ) memset( a , x ,sizeof(a) )
 14 #define rep( i ,x ,y ) for( int i = x ; i<=y ;i++ )
 15 #define lson  l ,mid ,pos<<1
 16 #define rson mid+1 ,r ,pos<<1|1
 17 using namespace std;
 18 typedef long long ll ;
 19 typedef pair<int ,int> pii;
 20 typedef pair<ll ,int> pli;
 21 const int inf = 0x3f3f3f3f;
 22 const int N = 1e5+100;
 23 const ll mod =1e9+7 ;
 24 char s[N],kkk;
 25 int n,m;
 26 int aa,bb,cc;
 27 int tree[4*N],ans[30],a[N];
 28 void push_up(int rt)
 29 {
 30     tree[rt]=tree[rt<<1]|tree[rt<<1|1];
 31 }
 32 void build(int rt,int l,int r)
 33 {
 34     if(l==r)
 35     {
 36         tree[rt]=(1<<a[l]);
 37         return;
 38     }
 39     int mid=l+r >>1;
 40     build(rt<<1,l,mid);
 41     build(rt<<1|1,mid+1,r);
 42     push_up(rt);
 43 }
 44 void update(int rt,int p,int x,int l,int r)
 45 {
 46     if(l==r)
 47     {
 48         tree[rt]=1<<x;
 49         return;
 50     }
 51     int mid=l+r>>1;
 52     if(p<=mid)
 53         update(rt<<1,p,x,l,mid);
 54     else
 55         update(rt<<1|1,p,x,mid+1,r);
 56     push_up(rt);
 57 }
 58 int query(int l,int r,int rt,int L,int R)
 59 {
 60     if(r<=R&&L<=l)
 61     {
 62         return tree[rt];
 63     }
 64     int mid=l+r>>1,ans=0;
 65     if(L<=mid)  ans|=query(l,mid,rt<<1,L,R);
 66     if(R>mid)   ans|=query(mid+1,r,rt<<1|1,L,R);
 67     return ans;
 68 }
 69 int solve(int x)
 70 {
 71     int ans=0;
 72     while(x)
 73     {
 74         if(x%2==1)  ans++;
 75         x/=2;
 76     }
 77     return ans;
 78 }
 79 int main()
 80 {
 81     scanf("%s",s+1);
 82     n=strlen(s+1);
 83     for(int i=1;i<=n;i++)
 84         a[i]=s[i]-'a';
 85     build(1,1,n);
 86     scanf("%d",&m);
 87     while(m--)
 88     {
 89         scanf("%d",&aa);
 90         if(aa==1)
 91         {
 92             scanf("%d %c",&bb,&kkk);
 93             update(1,bb,kkk-'a',1,n);
 94             s[bb]=kkk;
 95         }
 96         else
 97         {
 98             scanf("%d%d",&bb,&cc);
 99             printf("%d\n",solve(query(1,n,1,bb,cc)));
100         }
101     }
102 
103     return 0;
104 }

View Code

Codeforces Round #590 (Div. 3)

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Jacquelyn38 Jacquelyn38
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Stella981 Stella981
2年前
AndroidStudio封装SDK的那些事
<divclass"markdown\_views"<!flowchart箭头图标勿删<svgxmlns"http://www.w3.org/2000/svg"style"display:none;"<pathstrokelinecap"round"d"M5,00,2.55,5z"id"raphael
Wesley13 Wesley13
2年前
Java获得今日零时零分零秒的时间(Date型)
publicDatezeroTime()throwsParseException{    DatetimenewDate();    SimpleDateFormatsimpnewSimpleDateFormat("yyyyMMdd00:00:00");    SimpleDateFormatsimp2newS
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Stella981 Stella981
2年前
Nginx反向代理upstream模块介绍
!(https://oscimg.oschina.net/oscnet/1e67c46e359a4d6c8f36b590a372961f.gif)!(https://oscimg.oschina.net/oscnet/819eda5e7de54c23b54b04cfc00d3206.jpg)1.Nginx反
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
2个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这