周任务

算法任务：

主席树

具体任务：

HDU1394 权值线段树搞一搞： 求序列所有逆序对的个数，在根据首位交换，逆序对在本题中的个数变化N-2*a[i]-1的算式（首位的数放在最后的位置使得(比a[i]大的)逆序对多了N - a[i]个，少了(比a[i]小的)a[i] + 1个），求出min值

#include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int maxn = 1e6+5; int Tree[maxn<<2],N,a[maxn]; void Updata(int L,int R,int index,int pos){ if(L==R){ Tree[index] += 1; return; } int Mid = (L + R)>>1; if(pos<=Mid)Updata(L,Mid,index<<1,pos); else Updata(Mid + 1,R,index<<1|1,pos); Tree[index] = Tree[index<<1] + Tree[index<<1|1]; } long long Query(int L,int R,int index,int l,int r){ if(l<=L&R<=r){ return Tree[index]; } long long ans = 0; int Mid = (L + R)>>1; if(l<=Mid) ans += Query(L,Mid,index<<1,l,r); if(Mid<r) ans += Query(Mid + 1,R,index<<1|1,l,r); return ans; } int main(){ while(~scanf("%d",&N)){ memset(Tree,0,sizeof(Tree)); int x; long long ans = 0; for(int i = 1;i <= N;i++){ scanf("%d",&a[i]); ans += Query(1,N,1,a[i]+1,N); Updata(1,N,1,a[i]); } long long tool = ans; for(int i = 1;i<= N;i++){ ans += (N - 2*a[i] - 1); tool = min(ans,tool); } printf("%lld\n",tool); } return 0; }

POJ2104 主席树模板题没啥讲的

#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; const int maxn = 1e5 + 5; int ls[maxn<<5]={0},rs[maxn<<5]={0},sum[maxn<<5]={0},a[maxn],root[maxn],disc[maxn],now = 0; int BuildTree(int L,int R){ int pos = ++now; if(L==R)return pos; int Mid = (L + R)>>1; ls[pos] = BuildTree(L,Mid); rs[pos] = BuildTree(Mid + 1,R); return pos; } int Updata(int L,int R,int num,int front){ int pos = ++now; sum[pos] = sum[front] + 1; if(L==R) return pos; ls[pos] = ls[front];rs[pos] = rs[front]; int Mid = (L + R)>>1; if(num<=Mid) ls[pos] = Updata(L,Mid,num,ls[front]); else rs[pos] = Updata(Mid+1,R,num,rs[front]); return pos; } int Query(int L,int R,int K,int li,int ri){ if(L==R){ return disc[L]; } int x = sum[ls[ri]] - sum[ls[li]],Mid = (L + R)>>1; if(K<=x)return Query(L,Mid,K,ls[li],ls[ri]); else return Query(Mid+1,R,K-x,rs[li],rs[ri]); } int main(){ int N,M; scanf("%d%d",&N,&M); for(int i = 1;i <= N;i++){ scanf("%d",&a[i]); disc[i] = a[i]; } sort(disc + 1,disc + 1 + N); int cnt = unique(disc + 1,disc + 1 + N) - disc - 1; root[0] = BuildTree(1,cnt); for(int i = 1;i <= N;i++){ int pos = lower_bound(disc + 1,disc + 1 + cnt,a[i]) - disc; root[i] = Updata(1,cnt,pos,root[i-1]); } for(int i = 1;i <= M;i++){ int l,r,k; scanf("%d%d%d",&l,&r,&k); int ans = Query(1,cnt,k,root[l-1],root[r]); printf("%d\n",ans); } return 0; }

9012牛客多校训练营第九场H 就是主席树+前缀和+二分 代码（自己写的有亿点点bug懒得改了，其他dalao的代码）：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<map> #include<vector> #include<math.h> #include<queue> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fod(i,a,b) for(int i=a;i>=b;i--) #define me0(a) memset(a,0,sizeof(a)) #define me1(a) memset(a,-1,sizeof(a)) using namespace std; const int maxn = 4e6 + 100; const int INF = 0x3f3f3f3f; typedef long long LL; void read(LL& val) { int x = 0; int bz = 1; char c; for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') { bz = -1; c = getchar(); }for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48; val = x * bz; } LL n, q, a[maxn], b[maxn], sz, tot, root[maxn]; LL ls[maxn], rs[maxn], rt[maxn], val[maxn]; LL s[maxn];//s表示总和 LL sum[maxn]; void build(LL& o, int L, int R) { o = ++tot; val[o] = 0; s[o] = 0; if (L == R) return; int m = (L + R) >> 1; build(ls[o], L, m); build(rs[o], m + 1, R); } void update(LL& o, int L, int R, int last, int p) {//last 指的是上一个root的结点编号 o = ++tot; ls[o] = ls[last];// rs[o] = rs[last]; s[o] = s[last] + p; val[o] = val[last] + 1;//表示当前结点的重量增加1 if (L == R) return; int m = (L + R) >> 1; if (p <= m) update(ls[o], L, m, ls[last], p);//根据p值判断插入左子树还是右子树中 else update(rs[o], m + 1, R, rs[last], p); } int query(int ss, int tt, int L, int R, int k) {//区间起点、终点，查询的第k小 if (L == R) return L; int m = (L + R) >> 1; int cnt = val[ls[tt]] - val[ls[ss]];//结点的左子树相减，表示这个期间左子树上增加了多少个新的值，然后常规操作 if (k <= cnt) return query(ls[ss], ls[tt], L, m, k);//说明第k小在当前m的左边 else return query(rs[ss], rs[tt], m + 1, R, k - cnt); } LL query2(int ss, int tt, int L, int R, int k) {//查询前k小的和 if (L == R) { return (LL)k * L; } int m = (L + R) >> 1; int cnt = val[ls[tt]] - val[ls[ss]]; if (k > cnt) { return s[ls[tt]] - s[ls[ss]] + query2(rs[ss], rs[tt], m + 1, R, k - cnt); } else { return query2(ls[ss], ls[tt], L, m, k); } } void work() { LL ql, qr, x, y; read(ql); read(qr); read(x); read(y); double dpart = double(sum[qr] - sum[ql - 1]) / y * x;//切掉部分的长度和 LL L = 0, R = qr - ql + 1, m = 0, res = 0; LL num = qr - ql + 1;//总共num根竹子 LL Kth = a[ql], Ksum = 0, K = 0; while (L <= R) { m = (L + R) >> 1; Kth = query(root[ql - 1], root[qr], 1, sz, m);//找到m小,表示切到了第m小 Ksum = query2(root[ql - 1], root[qr], 1, sz, m);//前m小 Ksum = sum[qr] - sum[ql - 1] - Ksum - (num - m) * Kth;//切掉的部分 if ((double)Ksum - 0.00000001 >= dpart) { res = Kth; K = m; L = m + 1; } else { R = m - 1; } } double ans = Kth + ((double)Ksum - dpart) / (num - K); printf("%.9lf\n", ans); } int main() { //freopen("in.txt", "r", stdin); read(n); read(q); fo(i, 1, n) read(a[i]), sum[i] = sum[i - 1] + a[i], sz = max(sz, a[i]);//这里a[i]是连续的，不连续的需要另外做处理 tot = 0; build(root[0], 1, sz);//首先建立一个空树 fo(i, 1, n) update(root[i], 1, sz, root[i - 1], a[i]);//按输入顺序依次插入到相应的结点中去，并更改途中结点的信息（此时该结点有多少个子节点） while (q--) work(); return 0; }