Untitled
unknown
plain_text
a month ago
3.4 kB
9
Indexable
Never
#include <bits/stdc++.h> #define ll long long #define db long double #define sz(v) (int)v.size() #define all(v) v.begin(),v.end() #define e7na_leeh ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0); using namespace std; string di[] = {"L", "R", "U", "D", "UR", "UL", "DR", "DL"}; int dx[] = {0, 0, 1, -1, 1, 1, -1, -1}; int dy[] = {-1, 1, 0, 0, 1, -1, 1, -1}; const ll N = 1e5 + 5, mod = 1e9 + 7, inf = 1e18; ll n,ct=0; string s; vector<ll>v[26],fre(26); void add(ll ix,char c){ for (char i = 'a'; i <c ; ++i) { if(v[i-'a'].empty()||v[i-'a'].back()<ix) continue; auto it= lower_bound(all(v[i-'a']),ix)-v[i-'a'].begin(); ct+=sz(v[i-'a'])-it; } for (char i = c+1; i <='z' ; ++i) { if(v[i-'a'].empty()||v[i-'a'][0]>ix) continue; auto it= lower_bound(all(v[i-'a']),ix)-v[i-'a'].begin(); ct+=it; } } void del(ll ix,char c){ for (char i = 'a'; i <c ; ++i) { if(v[i-'a'].empty()||v[i-'a'].back()<ix) continue; auto it= lower_bound(all(v[i-'a']),ix)-v[i-'a'].begin(); ct-=sz(v[i-'a'])-it; } for (char i = c+1; i <='z' ; ++i) { if(v[i-'a'].empty()||v[i-'a'][0]>ix) continue; auto it= lower_bound(all(v[i-'a']),ix)-v[i-'a'].begin(); ct-=it; } } void solve() { cin>>n>>s; for (int i = 0; i <n ; ++i) { v[s[i]-'a'].push_back(i); for (char j = s[i]+1; j <='z' ; ++j) { ct+=fre[j-'a']; } fre[s[i]-'a']++; } ll q; cin>>q; while(q--){ ll typ; cin>>typ; if(typ==1){ ll ix; char c; cin>>ix>>c; --ix; if(s[ix]==c) continue; del(ix,s[ix]); auto it= lower_bound(all(v[s[ix]-'a']),ix); v[s[ix]-'a'].erase(it); s[ix]=c; if(v[c-'a'].empty()||v[c-'a'].back()<ix){ v[c-'a'].push_back(ix); } else { it = lower_bound(all(v[c - 'a']), ix); v[c - 'a'].insert(it, ix); } add(ix,c); } else if(typ==2){ ll l,r; cin>>l>>r; --l,--r; if(s[l]==s[r]) continue; auto it= lower_bound(all(v[s[l]-'a']),l); v[s[l]-'a'].erase(it); if(v[s[l]-'a'].empty()||v[s[l]-'a'].back()<r){ v[s[l]-'a'].push_back(r); } else { it = lower_bound(all(v[s[l] - 'a']), r); v[s[l] - 'a'].insert(it, r); } it= lower_bound(all(v[s[r]-'a']),r); v[s[r]-'a'].erase(it); if(v[s[r]-'a'].empty()||v[s[r]-'a'].back()<l){ v[s[r]-'a'].push_back(l); } else { it = lower_bound(all(v[s[r] - 'a']), l); v[s[r] - 'a'].insert(it, l); } del(l,s[l]); del(r,s[r]); swap(s[l],s[r]); add(l,s[l]); add(r,s[r]); } else{ cout<<ct<<'\n'; } } ct=0; for (int i = 0; i <26 ; ++i) { fre[i]=0; v[i].clear(); } } int main() { e7na_leeh int testCases = 1; cin >> testCases; while (testCases--) solve(); return 0; }
Leave a Comment