Untitled
unknown
plain_text
3 years ago
3.1 kB
6
Indexable
#include <iostream> #include <vector> using namespace std; int n,q; string s; vector<vector<int>> tree; vector<int> a(26,0); vector<int> change; int binpow (int a, int n) { int res = 1; while (n) { if (n & 1) res *= a; a *= a; n >>= 1; } return res; } int res(vector<int> &a){ long long ans=1; for (int i=0;i<26;i++){ ans+=bool(a[i]!=0); } for (int i=0;i<26;i++){ if (a[i]>0){ ans*=binpow(2,a[i]-1); ans%=1000000007; } } return (ans-1)%1000000007; } void build (int v, int tl, int tr) { if (tl == tr) tree[v][s[tl]-'a'] = 1; else { int tm = (tl + tr) / 2; build (v*2, tl, tm); build (v*2+1, tm+1, tr); vector<int> a2(26); for (int i=0;i<26;i++){ a2[i]=tree[v*2][i]+tree[v*2+1][i]; } tree[v] = a2; } } vector<int> get(int l, int r, int v, int tl, int tr) { if (l <= tl && tr <= r) { return tree[v]; } if (tr < l || r < tl) { return a; } //push(v, tl, tr); int tm = (tl + tr) / 2; vector<int> a2 = get(l, r, v * 2, tl, tm); vector<int> a3=get(l, r, v * 2 + 1, tm + 1, tr); for (int i=0;i<26;i++){ a2[i]+=a3[i]; } return a2; } int next(int k,int c){ int r=k; for (int i=0;i<c;i++){ if ((r+1)<26){ r++; } else{ r=0; } } return r; } void push(int v, int tl, int tr) { if (tl != tr - 1){ change[2 * v] = change[v]; change[2 * v + 1] = change[v]; } //как-то обновляем tree[v] change[v] = 0; } void upd(int l, int r, int c, int v, int tl, int tr) { if (l <= tl && tr <= r) { vector<int> a2(26,0); for (int i=0;i<26;i++){ // ?? я усталь ничего не понимать if (tree[v][i]!=0){ a2[next(i,c)] = tree[v][i]; // вроде бы тут все буквы меняем(если они есть) } } tree[v] = a2; return; } if (tr < l || r < tl) { return; } push(v,tl,tr); int tm = (tl + tr) / 2; upd(l, r, c, v * 2, tl, tm); upd(l, r, c, v * 2 + 1, tm + 1, tr); vector<int> a2(26); for (int i=0;i<26;i++){ a2[i]=tree[v*2][i]+tree[v*2+1][i]; } tree[v] = a2; } int main(){ cin>>n>>q; cin>>s; for (int i=0;i<4*n;i++){ tree.push_back(a); change.push_back(0); } build(1,0,n-1); int p,l,r,k; for (int i=0;i<q;i++){ cin>>p; if (p==2){ cin>>l>>r; vector<int> t=get(l,r,1,0,n-1); cout<<res(t); }else{ cin>>l>>r>>k; for (int j=l;j<r+1;j++){ change[j]=k; } upd(l, r, k, 1, 0, n-1) //upd(l, r, k, 1, 0, n-1); //for (int i=0;i<4*n;i++){ //for (int j=0;j<26;j++){ //cout<<"vertex "<<i<<" letter "<<j<<" count "<<tree[i][j]<<endl; //} //} } } return 0; }
Editor is loading...