Y15BeTa @ 2019-08-07 16:20:49
树状数组
开了longlong
用了读入优化
TLE
50pts
#include<cstdio>
#include<iostream>
#include<map>
#include<algorithm>
#define int long long
using namespace std;
typedef long long ll;
inline void input(ll &x){
ll ans=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
ans=ans*10+c-48;
c=getchar();
}
x=ans*f;
}
inline void output(ll x){
if(x<0)x=-x,putchar('-');
if(x>9)output(x/10);
putchar(x%10+48);
}
inline void writeln(ll x){
output(x);
putchar('\n');
}
int a[5000005],b[5000005],c[20000005],n,cnt;
map<int,int> sign;
inline int lowbit(int x){return x&(-x);}
inline void add(int k){
while(k<=n){
c[k]++;
k+=lowbit(k);
}
}
inline int query(int k){
int ans=0;
while(k){
ans+=c[k];
k-=lowbit(k);
}
return ans;
}
signed main(){
input(n);
for(int i=1;i<=n;i++){
input(a[i]);b[i]=a[i];
}
sort(b+1,b+n+1);
for(int i=1;i<=n;i++){
sign[b[i]]=++cnt;
}
int ans=0;
for(int i=n;i>=1;i--){
ans+=query(sign[a[i]]-1);
add(sign[a[i]]);
}
writeln(ans);
}by Y15BeTa @ 2019-08-07 16:45:43
@27__tmi 但是sort好像没有改值呀QwQ所以结构体的话是为什么呢
by Y15BeTa @ 2019-08-07 16:46:22
@Gang_Leader Orz谢巨佬但是......还是TLE（自闭
by Y15BeTa @ 2019-08-07 16:47:27
归并排序的话我不会啊QwQ，而且看题解里有用树状数组做的，我觉得树状数组优化一下应该有希望吧?
by K0stlin @ 2019-08-07 16:48:14
@TwxAqu 结构体x是a数组的位置，这样不用开map。
by Frozencode @ 2019-08-07 16:49:15
真的是妹子吗-_-
by K0stlin @ 2019-08-07 16:49:18
for(int i=n;i>=1;i--){ ans+=query(sign[i]-1); add(sign[i]); }
by K0stlin @ 2019-08-07 16:55:15
@TwxAqu
by Surpersolo @ 2019-08-08 15:24:21
#include<bits/stdc++.h>
using namespace std;
int n,a[500010],k[500010];
long long s;
void vgg(int b,int e)
{
if(b==e)return;
int m=(b+e)/2;
vgg(b,m);
vgg(m+1,e);
int i=b,j=m+1,p=b;
while(i<=m&&j<=e)
{
if(a[i]<=a[j])k[p++]=a[i++];
else
{
k[p++]=a[j++];
s+=(long long)m-i+1;
}
}
while(i<=m)k[p++]=a[i++];
while(j<=e)k[p++]=a[j++];
for(int i=b;i<=e;i++)a[i]=k[i];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
vgg(1,n);
cout<<s;
return 0;
}拿走不谢，我也是想了好久
by tohmasu @ 2019-08-14 20:27:03
妹子你之前好像也是在这题下面发了个帖说你是汉子...