[POI2012]Letters
树状数组求逆序对
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include<set> #include<map> #include<list> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<cctype> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define qread(x) x=read() #define lowbit(x) (x&-x) #define mes(x,y) memset(x,y,sizeof(x)) #define mpy(x,y) memcpy(x,y,sizeof(x)) #define Maxn 1048576 #define Maxs 26 #define INF 2147483647 inline long long read(){ long long f=1,x=0;char ch; while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return f*x; } long long n,ans,f[Maxn+1],map[Maxn+1]; void add(long long x,long long c){ while(x<=n){ f[x]+=c; x+=lowbit(x); } } long long get(long long x){ long long ret=0; while(x>0){ ret+=f[x]; x-=lowbit(x); } return ret; } char s[Maxn+1]; std::vector<long long>a[Maxs+1],b[Maxs+1]; int main(){ qread(n); scanf("%s",s+1); for(long long i=1;i<=n;i++)a[s[i]-'A'+1].push_back(i); scanf("%s",s+1); for(long long i=1;i<=n;i++)b[s[i]-'A'+1].push_back(i); for(long long i=1;i<=26;i++){ for(long long j=0;j<a[i].size();j++)map[a[i][j]]=b[i][j]; } ans=0; for(long long i=1;i<=n;i++){ ans+=i-1-get(map[i]); add(map[i],1); } printf("%lld\n",ans); } |