luogu1966 火柴排队(离散化+树状数组)
标签：oid name ret efi fine long bit void color
由于是一个二次函数的关系，所以易证应该尽量让两组的顺序相同
然后就离散化乱搞几发，最后就变成了求逆序对的数量了
1 #include 2 #define pa pair 3 #define ll long long
4 using namespace std;
5 const int maxn=100010,mod=99999997;
6
7 inline ll rd(){
8 ll x=0;char c=getchar();int neg=1;
9 while(c‘0‘||c>‘9‘){if(c==‘-‘) neg=-1;c=getchar();}
10 while(c>=‘0‘&&c‘9‘) x=x*10+c-‘0‘,c=getchar();
11 return x*neg;
12 }
13
14 int N;
15 pa h1[maxn],h2[maxn];
16 int nh[maxn],rank[maxn];
17 int tr[maxn];
18
19 inline int lowbit(int x){return x&(-x);}
20
21 inline void add(int x,int y){
22 for(;xmod;
23 }
24 inline int query(int x){
25 int re=0;for(;x;x-=lowbit(x)) re=(re+tr[x])%mod;return re;
26 }
27
28 int main(){
29 int i,j,k;
30 N=rd();
31 for(i=1;imake_pair(rd(),i);
32 for(i=1;imake_pair(rd(),i);
33 sort(h1+1,h1+N+1);sort(h2+1,h2+N+1);
34 for(i=1;i){
35 rank[i]=h1[i].second;
36 }for(i=1;i){
37 nh[h2[i].second]=rank[i];
38 }int ans=0;
39 for(i=N;i;i--){
40 ans=(ans+query(nh[i]))%mod;
41 add(nh[i],1);
42 }printf("%d\n",ans);
43 return 0;
44 }
luogu1966 火柴排队(离散化+树状数组)
标签：oid name ret efi fine long bit void color
原文地址：https://www.cnblogs.com/Ressed/p/9643860.html
评论