Untitled

 avatar
unknown
plain_text
3 years ago
3.1 kB
5
Indexable
#include <iostream>
#include <vector>

using namespace std;
int n,q;
string s;
vector<vector<int>> tree;
vector<int> a(26,0);
vector<int> mod;

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 (mod[v] != 0 && v * 2 + 1 < 400004) {
        
        mod[v * 2] = mod[v * 2 + 1] = mod[v];
        mod[v] = 0;

        //int tm = (tl + tr) / 2;
        //tree[v * 2] = (tm - tl + 1) * mod[v * 2];
        //tree[v * 2 + 1] = (tr - tm) * mod[v * 2 + 1];
    }
}

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];
            }
        } 
        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);
        if (i<n) mod.push_back(0);
    }
    build(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;
        //}
    //}
    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++){
                mod[j]=k;
            }
            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...