fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define TIME (1.0* clock()/CLOCKS_PER_SEC)
  3. #define pb push_back
  4. #define eb emplace_back
  5. #define id1 (id<<1)
  6. #define id2 (id<<1)|1
  7. #define ll long long
  8. #define ii pair<int,int>
  9. #define vi vector<int>
  10. #define vii vector<pair<int,int>> 
  11. #define vl vector<long long>
  12. #define vll vector <pair<ll,ll>>
  13. #define li pair<long long,int>
  14. #define vil vector <pair<int,ll>>
  15. #define db double
  16. #define ff first
  17. #define ss second
  18. #define lb lower_bound
  19. #define ub upper_bound
  20. #define FOR(i, a, b) for (int i = (a); i <=(b); i++)
  21. #define F0R(i, a) FOR(i, 0, a-1)
  22. #define ROF(i, a, b) for (int i = (b); i >= (a); i--)
  23. #define R0F(i, a) ROF(i, 0, a-1)
  24. #define rep(a) F0R(_, a)
  25. #define each(a, x) for (auto &a : x)
  26. #define ALL(x) (x).begin(),(x).end()
  27. #define pq priority_queue <li, vector <li>, greater <li>> 
  28. using namespace std;
  29. const int maxn=200005;
  30. // k ≤ 10
  31. int n, m, k;
  32. string s;
  33. int lz[maxn << 2]; 
  34.  
  35. struct Node {
  36.     int fir, las;
  37.     int f[10][10];
  38.     int len;
  39. } t[maxn << 2];
  40.  
  41. Node merge(Node a, Node b) {
  42.     Node res;
  43.     res.fir = a.fir;
  44.     res.las = b.las;
  45.     res.len = a.len + b.len;
  46.  
  47.     for(int i = 0; i < k; i++) for(int j = 0; j < k; j++)
  48.         res.f[i][j] = a.f[i][j] + b.f[i][j];
  49.     if(a.len > 0 && b.len > 0) {
  50.         res.f[a.las][b.fir]++;
  51.     }
  52.     return res;
  53. }
  54.  
  55. void build(int id, int l, int r) {
  56.     lz[id] = -1;
  57.     if(l == r) {
  58.         int c = s[l] - 'a';
  59.         t[id].fir = t[id].las = c;
  60.         t[id].len = 1;
  61.         for(int i=0;i<k;i++) for(int j=0;j<k;j++) t[id].f[i][j]=0;
  62.         return;
  63.     }
  64.     int mid = (l + r) >> 1;
  65.     build(id1, l, mid);
  66.     build(id2, mid+1, r);
  67.     t[id] = merge(t[id1], t[id2]);
  68. }
  69.  
  70. void push(int id, int l, int r) {
  71.     if(lz[id] != -1) {
  72.         int c = lz[id];
  73.         t[id].fir = t[id].las = c;
  74.  
  75.         for(int i=0;i<k;i++) for(int j=0;j<k;j++) t[id].f[i][j]=0;
  76.         if(t[id].len > 1) t[id].f[c][c] = t[id].len - 1;
  77.         if(l != r) {
  78.             lz[id1] = c;
  79.             lz[id2] = c;
  80.         }
  81.         lz[id] = -1;
  82.     }
  83. }
  84.  
  85. void update(int id, int l, int r, int u, int v, int c) {
  86.     push(id, l, r);
  87.     if(v < l || r < u) return;
  88.     if(u <= l && r <= v) {
  89.         lz[id] = c;
  90.         push(id, l, r);
  91.         return;
  92.     }
  93.     int mid = (l + r) >> 1;
  94.     update(id1, l, mid, u, v, c);
  95.     update(id2, mid+1, r, u, v, c);
  96.     t[id] = merge(t[id1], t[id2]);
  97. }
  98.  
  99. int query(const string &p) {
  100.     vector<int> pos(k);
  101.     for(int i=0;i<k;i++) pos[p[i]-'a'] = i;
  102.     int res = 0;
  103.     for(int i=0;i<k;i++) for(int j=0;j<k;j++) {
  104.         int val = (pos[i] >= pos[j]) ? 1 : 0;
  105.         res += t[1].f[i][j] * val;
  106.     }
  107.     return res;
  108. }
  109.  
  110. void solve(){
  111.   cin>>n>>m>>k;
  112.   cin>>s;
  113.   s = ' ' + s;
  114.   build(1,1,n);
  115.   while(m--) {
  116.     int type;
  117.     cin>>type;
  118.     if(type==1) {
  119.       int l,r; char x;
  120.       cin>>l>>r>>x;
  121.       update(1,1,n,l,r, x - 'a');
  122.     } else {
  123.       string p;
  124.       cin>>p;
  125.       cout<<query(p)+1<< '\n';
  126.     }
  127.   }
  128. }
  129.  
  130. int main(){
  131.   ios::sync_with_stdio(false);
  132.   cin.tie(NULL);
  133.   if(fopen("TASK.INP","r")){
  134.     freopen("TASK.INP","r",stdin);
  135.     freopen("TASK.OUT","w",stdout);
  136.   }
  137.   solve();
  138.   cerr<<"Time elapsed "<<TIME<<"s.";
  139.   return 0;
  140. }
Success #stdin #stdout #stderr 0.01s 5844KB
comments (?)
stdin
copy 
7 4 3
abacaba
1 3 5 b
2 abc
1 4 4 c
2 cba
stdout
copy 
6
5
stderr
copy 
Time elapsed 0.00696s.
https://ideone.com/QH8t5r
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!