shift and算法-白红宇

shift and算法

阅读量：5095 次

发布时间：2019-06-13

本文共 1772 字，大约阅读时间需要 5 分钟。

1. CF 914F Substrings in a String

大意: 给定一个串s, q个询问, (1)单点修改, (2)询问[l,r]范围内串y的出现次数.

shift and算法板子题

#pragma GCC optimize("Ofast")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#pragma GCC optimize("unroll-loops")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define REP(i,a,n) for(int i=a;i<=n;++i)#define PER(i,a,n) for(int i=n;i>=a;--i)#define hr putchar(10)#define pb push_back#define lc (o<<1)#define rc (lc|1)#define mid ((l+r)>>1)#define ls lc,l,mid#define rs rc,mid+1,r#define x first#define y second#define io std::ios::sync_with_stdio(false)#define endl '\n'#define DB(a) ({REP(__i,1,n) cout<
                
                 <<' ';hr;})using namespace std;typedef long long ll;typedef pair
                 
                   pii;const int P = 1e9+7, INF = 0x3f3f3f3f;ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}//head#ifdef ONLINE_JUDGEconst int N = 1e5+10;#elseconst int N = 11;#endifint n, m;char s[N], buf[N];bitset
                  
                    ch[26], ans;int main() { scanf("%s", s); n = strlen(s); REP(i,0,n-1) ch[s[i]-'a'].set(i); scanf("%d", &m); REP(i,1,m) { int op, x, y; char c; scanf("%d%d", &op, &x),--x; if (op==1) { scanf(" %c", &c); ch[s[x]-'a'].reset(x); s[x] = c; ch[s[x]-'a'].set(x); } else { scanf("%d%s", &y, buf),--y; int len = strlen(buf); if (y-x+1
                   
                    >i; int ret = (ans>>x).count()-(ans>>y-len+2).count(); printf("%d\n", ret); } }}