性病医院网站优化服务商,青岛网站建设详细内容,东莞建设银行网点查询,WordPress全局响应Problem - 1579E2 - Codeforces Array Optimization by Deque - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 树状数组解法
将 a i a_i ai插入到队头#xff0c;贡献为#xff1a;原队列中所有比 a i a_i ai小的数的数量将 a i a_i ai插入到队尾#xff0c;贡献为贡献为原队列中所有比 a i a_i ai小的数的数量将 a i a_i ai插入到队尾贡献为原队列中所有比 a i a_i ai大的数的数量
可以发现对于每一次插入a值影响插入的只跟已经放入的大于a或小于a的数量有关。
需要一个数据结构满足动态修改、查询。可以发现树状数组可以做这些操作不过 a i a_i ai较大开不下数组可以离散化。
在离散化后本题转为查询 a i a_i ai前面的数量和后面的数量大于/小于。如果前面的数量小就插前面否则插入后面将答案进行更新。
#include iostream
#include vector
#include string
#include cstring
#include set
#include map
#include queue
#include ctime
#include random
#include sstream
#include numeric
#include stdio.h
#include functional
#include bitset
#include algorithm
using namespace std;#define Multiple_groups_of_examples
#define int_to_long_long
#define IOS std::cout.tie(0);std::cin.tie(0)-sync_with_stdio(false); // 开IOS需要保证只使用Cpp io流 *
#define dbgnb(a) std::cout #a a \n;
#define dbgtt cout !!!test!!! \n;
#define rep(i,x,n) for(int i x; i n; i)#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs secondtypedef long long LL;
#ifdef int_to_long_long
#define int long long
#endif
typedef pairint,int PII;const int INF 0x3f3f3f3f;
const int N 2e5 21;template class T
struct Fenwick { int n;vectorT a;Fenwick(const int n 0) : n(n), a(n, T()) {}void modify(int i, T x) {for (i; i n; i i -i) {a[i - 1] x;}}T get(int i) {T res T();for (; i 0; i - i -i) {res a[i - 1];}return res;}T sum(int l, int r) { // [l, r] *这里已经改过return get(r 1) - get(l);}int kth(T k) {int x 0;for (int i 1 __lg(n); i; i 1) {if (x i n k a[x i - 1]) {x i;k - a[x - 1];}}return x;}
};void inpfile();
void solve() {int n; cinn;vectorint a(n);for(auto t: a) cint;// 离散化vectorint id(a);sort(all(id));id.erase(unique(all(id)), id.end());vectorint last(n);for(int i 0; i n; i) last[i] lower_bound(all(id), a[i]) - id.begin() 1;Fenwickint tr(n 21);int sum 0;for(int i 0; i n; i) {// lv表示插入队首rv表示插入队尾的逆序对值int lv tr.sum(1, last[i] - 1), rv tr.sum(last[i] 1, n 20);sum min(lv, rv);tr.modify(last[i], 1);}coutsumendl;}
#ifdef int_to_long_long
signed main()
#else
int main()
#endif{#ifdef Multiple_groups_of_examplesint T; cinT;while(T--)#endifsolve();return 0;
}
void inpfile() {#define mytest#ifdef mytestfreopen(ANSWER.txt, w,stdout);#endif
}pbds 解法
pbds库学习笔记(优先队列、平衡树、哈希表) - 知乎 (zhihu.com)
发现核心就是求排名平衡树即可。这里提供pbds的代码
#include iostream
#include vector
#include string
#include cstring
#include set
#include map
#include queue
#include ctime
#include random
#include sstream
#include numeric
#include stdio.h
#include functional
#include bitset
#include algorithm// pbds
#include bits/extc.h
using namespace __gnu_cxx;
using namespace __gnu_pbds;
using namespace std;#define Multiple_groups_of_examples
#define int_to_long_long
#define IOS std::cout.tie(0);std::cin.tie(0)-sync_with_stdio(false); // 开IOS需要保证只使用Cpp io流 *
#define dbgnb(a) std::cout #a a \n;
#define dbgtt cout !!!test!!! \n;
#define rep(i,x,n) for(int i x; i n; i)#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs secondtypedef long long LL;
#ifdef int_to_long_long
#define int long long
#endif
typedef pairint,int PII;const int INF 0x3f3f3f3f;
const int N 2e5 21;
// pbds
typedef treePII, null_type, lessPII, rb_tree_tag, tree_order_statistics_node_update Tree;
void inpfile();
void solve() {int n; cinn;Tree tr;int sum 0;for(int i 0; i n; i) {int t; cint;int lv tr.order_of_key({t, 0}), rv i - tr.order_of_key({t, n});sum min(lv, rv);tr.insert({t, i});}coutsumendl;
}
#ifdef int_to_long_long
signed main()
#else
int main()
#endif{#ifdef Multiple_groups_of_examplesint T; cinT;while(T--)#endifsolve();return 0;
}
void inpfile() {#define mytest#ifdef mytestfreopen(ANSWER.txt, w,stdout);#endif
}pbds库学习笔记(优先队列、平衡树、哈希表) - 知乎 (zhihu.com)
