营销 网站制作,公司邮箱密码忘记了怎么办,江苏宏澄建设有限公司网站,物流网信息平台感觉这东西就是每棵线段树管的区间变了#xff0c;以前学的时候线段树总是只管一个点或者管#xff08;1-i#xff09;这些点#xff0c;但是这东西如果加上树状数组的思想#xff0c;每棵线段树管#xff08; i-(i-i)1 ~ i #xff09;这些区间#xff0c;那么动…感觉这东西就是每棵线段树管的区间变了以前学的时候线段树总是只管一个点或者管1-i这些点但是这东西如果加上树状数组的思想每棵线段树管 i-(i-i)1 ~ i 这些区间那么动态修改单点就不用nlog修改只用改这个点在那log棵线段树改log*log次查询的话变慢了点之前的 log变成了 log * log 精品博客 讲的真的很好 感谢大佬 博客园 TaylorSwift13 的 树状数组套权值线段树 动态逆序对 代码
Dynamic Rankings 代码 #include iostream
#include algorithm
#include cstring
#include sstream
using namespace std;
typedef long long LL;
const int N 5e5 4;
int n, m;
int a[N], f[N];
int rt[N], ls[N6], rs[N6], val[N6], idx 0;namespace seg
{void modify(int u, int l, int r, int x, int f){if(!u) u idx;val[u] f;if(lr)return ;int mid lr1;x mid ? modify(ls[u], l, mid, x, f) : modify(rs[u], mid1, r, x, f);}int quary(int u, int l, int r, int L, int R){if(!u||Lr||Rl)return 0;if(LlRr)return val[u];int mid lr1;return quary(ls[u], l, mid, L, R) quary(rs[u], mid1, r, L, R);}
};namespace tree
{int quary(int u, int l, int r){int sum 0;for(int x u;x 1;x - (x-x))sum seg::quary(rt[x], 0, n1, l, r);return sum;}void modify(int u,int g, int f){for(int x u;x n;x (x-x))seg::modify(rt[x], 0, n1, g, f);}
};namespace tr{int tr[N]{};void modify(int u,int f){while(un1)tr[u]f,u(u-u);}int quary(int u){int sum0;while(u)sumtr[u],u-(u-u);return sum;}
}int main()
{scanf(%d%d,n, m);for(int i 1;i n;i )scanf(%d,a i);LL ans 0;for(int i 1;i n;i ){ans tree::quary(i-1, a[i]1, n1);tree::modify(i, a[i], 1);tr::modify(a[i], 1);f[a[i]] i;}while(m --){int x;scanf(%d, x); coutansendl;ans - tree::quary(f[x]-1, x1, n1);ans - tr::quary(x-1) - tree::quary(f[x]-1, 0, x-1);tree::modify(f[x], x, -1);tr::modify(x, -1);}return 0;
}#include iostream
#include algorithm
#include cstring
#include sstream
using namespace std;typedef long long ll;
const int N 1e5 4;
int n, m;
int rt[N], ls[N9], rs[N9], val[N9], idx;
int x[N], cntx, y[N], cnty, a[N];int quary(int l, int r, int k)
{ if(l r)return l;int sum 0;for(int i 0;i cntx ;i )sum - val[ls[x[i]]];for(int i 0;i cnty ;i )sum val[ls[y[i]]];if(sum k){for(int i 0;i cntx ;i )x[i] ls[x[i]];for(int i 0;i cnty ;i )y[i] ls[y[i]];return quary(l, lr1, k);}else {for(int i 0;i cntx ;i )x[i] rs[x[i]];for(int i 0;i cnty ;i )y[i] rs[y[i]];return quary((lr1) 1, r, k - sum);}
}void modify(int u, int l, int r, int x, int f)
{if(!u)u idx;val[u] f;if(l r)return ;int mid lr1;x mid ? modify(ls[u], l, mid, x, f) : modify(rs[u], mid1, r, x, f);
}int main()
{ scanf(%d%d, n, m);for(int i 1;i n;i ){scanf(%d, ai);for(int u i;u n;u (u-u))modify(rt[u], 0, 1e9, a[i], 1);}while(m --){char c[2];int l, r, k;scanf(%s%d%d, c, l, r);if(c[0]Q){scanf(%d, k);cntx cnty 0;for(int j l-1;j 1;j - (j-j)) x[cntx] rt[j];for(int u r;u 1; u - (u-u)) y[cnty] rt[u];coutquary(0, 1e9, k)endl;}else{for(int u l;u n;u (u-u))modify(rt[u], 0, 1e9, a[l], -1);a[l] r;for(int u l;u n;u (u-u))modify(rt[u], 0, 1e9, a[l], 1);}}return 0;
}
