电商网站开发教材,怎么用电脑做网站,坦洲网站建设,泰安网站建设个人工作室Problem - 1915F - Codeforces
题意 给一些(l,r)找到所有能够包含(l,r)的数目
引入
也就是找逆序对个数
要用到归并排序中的思想#xff1a;
//https://www.luogu.com.cn/problem/P1216
#includeiostream
#includecstdio
#includestack
#include…Problem - 1915F - Codeforces
题意 给一些(l,r)找到所有能够包含(l,r)的数目
引入
也就是找逆序对个数
要用到归并排序中的思想
//https://www.luogu.com.cn/problem/P1216
#includeiostream
#includecstdio
#includestack
#includevector
#includealgorithm
#includecmath
#includequeue
#includecstring
#includemap
#includeset
#includevector
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pairint, int PII;
const int INF 1e18 10;
const int N 2e5 10;
const int M 1e7 10;
const int mod 1e9 7;
int n, m, k, ans;
int qcal(int a, int b) { int res 1; while (b) { if (b 1) res res * a % mod; b 1; a a * a % mod; } return res; }
int a[N];
bool is_prime(int n) { if (n 2) return false; for (int i 2; i n / i; i) { if (n % i 0) { return false; } }return true; }
int b[N];
void merge(int l,int r)
{// 拆分if(l r) return;int mid l r 1;merge(l,mid);merge(mid1,r);// 合并int i l,j mid 1,k l;while(i mid j r){if(a[i] a[j]) b[k ] a[i ];else b[k ] a[j ];}while(i mid) b[k ] a[i ];while(j r) b[k ] a[j ];for(i l;i r;i ) a[i] b[i];
}void gzy()
{cin n;for(int i 1;i n;i ) cin a[i];merge(1,n);for(int i 1;i n;i ) cout a[i] ;puts();
}
signed main()
{IOS;int _ 1; while (_--) gzy();return 0;
}
思路
只需要加一个 sum mid - i 1;
code
#includeiostream
#includecstdio
#includestack
#includevector
#includealgorithm
#includecmath
#includequeue
#includecstring
#includemap
#includeset
#includevector
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pairint, int PII;
const int INF 1e18 10;
const int N 5e5 10;
const int M 1e7 10;
const int mod 1e9 7;
int n, m, k, ans;
int qcal(int a, int b) { int res 1; while (b) { if (b 1) res res * a % mod; b 1; a a * a % mod; } return res; }
int a[N];
bool is_prime(int n) { if (n 2) return false; for (int i 2; i n / i; i) { if (n % i 0) { return false; } }return true; }
int b[N];
int sum 0;
void merge(int l,int r)
{// 拆分if(l r) return;int mid l r 1;merge(l,mid);merge(mid1,r);// 合并int i l,j mid 1,k l;while(i mid j r){if(a[i] a[j]){b[k ] a[i ];}else {sum mid - i 1;b[k ] a[j ];}}while(i mid) b[k ] a[i ];while(j r) b[k ] a[j ];for(i l;i r;i ) a[i] b[i];
}void gzy()
{cin n;for(int i 1;i n;i ) cin a[i];merge(1,n);// for(int i 1;i n;i ) cout a[i] ;// puts();cout sum endl;
}
signed main()
{IOS;int _ 1; while (_--) gzy();return 0;
}
思路
就是对first排序之后 找到second中的逆序对个数 code
//https://www.luogu.com.cn/problem/P1216
#includeiostream
#includecstdio
#includestack
#includevector
#includealgorithm
#includecmath
#includequeue
#includecstring
#includemap
#includeset
#includevector
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pairint, int PII;
const int INF 1e18 10;
const int N 5e5 10;
const int M 1e7 10;
const int mod 1e9 7;
int n, m, k, ans;
int qcal(int a, int b) { int res 1; while (b) { if (b 1) res res * a % mod; b 1; a a * a % mod; } return res; }
PII d[N];
bool is_prime(int n) { if (n 2) return false; for (int i 2; i n / i; i) { if (n % i 0) { return false; } }return true; }
int a[N],b[N];
int sum 0;
void merge(int l,int r)
{// 拆分if(l r) return;int mid l r 1;merge(l,mid);merge(mid1,r);// 合并int i l,j mid 1,k l;while(i mid j r){if(a[i] a[j]){b[k ] a[i ]; }else {sum mid - i 1;b[k ] a[j ];}}while(i mid) b[k ] a[i ];while(j r) b[k ] a[j ];for(i l;i r;i ) a[i] b[i];
}void gzy()
{sum 0;cin n;for(int i 1;i n;i ) cin d[i].first d[i].second;sort(d1,d1n);for(int i 1;i n;i ) a[i] d[i].second;merge(1,n);cout sum endl;
}
signed main()
{IOS;int _ 1; cin _;while (_--) gzy();return 0;
}
