3 条题解
-
0
#include<bits/stdc++.h> using namespace std; typedef long long ll; int n,q,a[100010],p[500010]; int lowbit(int x){ return x&(-x); } struct BIT{ int tr[100010]; void add(int x,int v){ for(int i=x;i<=n;i+=lowbit(i)){ tr[i]+=v; } } int find(int x){ int ans=0; for(int i=x;i;i-=lowbit(i)){ ans+=tr[i]; } return ans; } }tr,tr2; int ans[100010]; struct Q{ int l,r,v,op,k,id; }qq[400010],u1[400010],u2[400010]; void solve(int l,int r,int x,int y){ if(x>y)return ; int mid=(l+r)>>1; int n1=0,n2=0; for(int i=x;i<=y;i++){ if(!qq[i].id){ if(qq[i].r<=mid)tr.add(qq[i].l,qq[i].v),u1[++n1]=qq[i]; else tr2.add(qq[i].l,qq[i].v),u2[++n2]=qq[i]; } else{ if(qq[i].v<=mid){ if(qq[i].op==1)qq[i].k+=tr2.find(qq[i].r)-tr2.find(qq[i].l-1); if(l==r)qq[i].k+=tr.find(qq[i].r)-tr.find(qq[i].l-1); u1[++n1]=qq[i]; } else{ if(qq[i].op==-1)qq[i].k+=tr.find(qq[i].r)-tr.find(qq[i].l-1); u2[++n2]=qq[i]; } } } for(int i=1;i<=n1;i++)if(!u1[i].id)tr.add(u1[i].l,-u1[i].v); for(int i=1;i<=n2;i++)if(!u2[i].id)tr2.add(u2[i].l,-u2[i].v); if(l==r){ for(int i=x;i<=y;i++){ ans[qq[i].id]+=qq[i].k; } return ; } int id=x; for(int i=1;i<=n1;i++)qq[id++]=u1[i]; for(int i=1;i<=n2;i++)qq[id++]=u2[i]; solve(l,mid,x,x+n1-1); solve(mid+1,r,x+n1,y); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>q; int id=0; ll res=0; for(int i=1;i<=n;i++){ cin>>a[i]; p[a[i]]=i; res+=i-1-tr.find(a[i]); tr.add(a[i],1); qq[++id]={i,a[i],1,0,0,0}; } memset(tr.tr,0,sizeof(tr.tr)); for(int i=1;i<=q;i++){ int x; cin>>x; x=p[x]; if(x>1)qq[++id]={1,x-1,a[x]+1,1,0,i}; if(x<n)qq[++id]={x+1,n,a[x]-1,-1,0,i}; qq[++id]={x,a[x],-1,0,0,0}; } solve(1,n,1,id); for(int i=1;i<=q;i++){ cout<<res<<'\n'; res-=ans[i]; } return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:08:34
P3157 [CQOI2011] 动态逆序对
树状数组套权值线段树（700ms）
C84 树状数组套权值线段树 P3157 [CQOI2011] 动态逆序对
#include <bits/stdc++.h> using namespace std; #define mid ((l + r) >> 1) #define ls (tr[u].lc) #define rs (tr[u].rc) const int N = 1e5 + 10; struct trnode { int lc, rc, s; } tr[N * 300]; int n, m, a[N], pos[N], rt[N], tot; long long ans; void change(int &u, int l, int r, int x, int k) { if (!u) u = ++tot, tr[tot] = trnode{0, 0, 0}; tr[u].s += k; if (l == r) return; if (x <= mid) change(ls, l, mid, x, k); else change(rs, mid + 1, r, x, k); } void change(int u, int x, int k) { for (; u <= n; u += (u & -u)) change(rt[u], 1, n, x, k); } int qmore(int u, int l, int r, int v) { if (!u) return 0; if (v < l) return tr[u].s; int res = 0; res += qmore(rs, mid + 1, r, v); if (v <= mid) res += qmore(ls, l, mid, v); return res; } int qmore(int x, int v) { int res = 0; for (; x >= 1; x -= (x & -x)) res += qmore(rt[x], 1, n, v); return res; } int qless(int u, int l, int r, int v) { if (!u) return 0; if (v > r) return tr[u].s; int res = 0; res += qless(ls, l, mid, v); if (v > mid) res += qless(rs, mid + 1, r, v); return res; } int qless(int x, int v) { int res = 0; for (; x >= 1; x -= (x & -x)) res += qless(rt[x], 1, n, v); return res; } int main() { scanf("%d%d", &n, &m); memset(rt, 0, sizeof(rt)); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); pos[a[i]] = i; ans += qmore(i - 1, a[i]); change(i, a[i], 1); } while (m--) { printf("%lld\n", ans); int v; scanf("%d", &v); ans -= qmore(pos[v] - 1, v) + qless(n, v) - qless(pos[v] - 1, v); change(pos[v], v, -1); } return 0; }二维线段树（1700ms，超时2个点）
C98 CDQ 分治+树状数组 P3157 [CQOI2011] 动态逆序对
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; #define mid ((l + r) >> 1) struct node { int a, b; } a[N]; int n, m, bb[N], bn, pos[N]; int root, totx, toty, xls[N * 2], xrs[N * 2]; int rt[N * 2], yls[N * 2 * 200], yrs[N * 2 * 200], d[N * 2 * 200]; void changeY(int &p, int l, int r, int y, int c) { if (!p) p = ++toty; d[p] += c; if (l == r) return; if (y <= mid) changeY(yls[p], l, mid, y, c); else changeY(yrs[p], mid + 1, r - 1, y, c); } void changeX(int &p, int l, int r, int x, int y, int c) { if (!p) p = ++totx; changeY(rt[p], 1, bn, y, c); if (l == r) return; if (x <= mid) changeX(xls[p], l, mid, x, y, c); else changeX(xrs[p], mid + 1, r, x, y, c); } int queryY(int p, int l, int r, int y1, int y2) { if (!p) return 0; if (y1 <= l && r <= y2) return d[p]; int res = 0; if (y1 <= mid) res += queryY(yls[p], l, mid, y1, y2); if (y2 > mid) res += queryY(yrs[p], mid + (l != mid), r, y1, y2); return res; } int queryX(int p, int l, int r, int x1, int x2, int y1, int y2) { if (!p) return 0; if (x1 <= l && r <= x2) return queryY(rt[p], 1, bn, y1, y2); int res = 0; if (x1 <= mid) res += queryX(xls[p], l, mid, x1, x2, y1, y2); if (x2 > mid) res += queryX(xrs[p], mid + 1, r, x1, x2, y1, y2); return res; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i].b), a[i].a = i; for (int i = 1; i <= n; i++) bb[i] = a[i].b; sort(bb + 1, bb + n + 1); bn = unique(bb + 1, bb + 1 + n) - bb - 1; for (int i = 1; i <= n; i++) { a[i].b = lower_bound(bb + 1, bb + bn + 1, a[i].b) - bb; pos[a[i].b] = i; } root = totx = toty = 0; memset(rt, 0, sizeof(rt)); memset(d, 0, sizeof(d)); for (int i = 1; i <= n; i++) changeX(root, 1, n, a[i].a, a[i].b, 1); long long ans = 0; for (int i = 1; i <= n; i++) { ans += queryX(root, 1, n, 1, a[i].a - 1, a[i].b + 1, bn); } while (m--) { int x; scanf("%d", &x); x = lower_bound(bb + 1, bb + bn + 1, x) - bb; int i = pos[x]; printf("%lld\n", ans); ans = ans - queryX(root, 1, n, 1, a[i].a - 1, a[i].b + 1, bn) - queryX(root, 1, n, a[i].a + 1, n, 1, a[i].b - 1); changeX(root, 1, n, a[i].a, a[i].b, -1); } return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:08:06
C84 树状数组套权值线段树 P3157 [CQOI2011] 动态逆序对
C98 CDQ 分治+树状数组 P3157 [CQOI2011] 动态逆序对
树状数组套线段树（700ms）#include<bits/stdc++.h> using namespace std; #define mid ((l+r)>>1) #define ls (tr[ u ].lc) #define rs (tr[ u ].rc) const int N=1e5+10; struct trnode{int lc,rc,s;}tr[N*300]; int n,m,a[N],pos[N],rt[N],tot; long long ans; void change(int &u,int l,int r,int x,int k) { if(!u)u=++tot,tr[tot]=trnode{0,0,0}; tr[ u ].s+=k; if(l==r)return; if(x<=mid) change(ls,l,mid,x,k); else change(rs,mid+1,r,x,k); } void change(int u,int x,int k){for(;u<=n;u+=(u&-u))change(rt[ u ],1,n,x,k);} int qmore(int u,int l,int r,int v) { if(!u) return 0; if(v<l) return tr[ u ].s; int res=0; res+=qmore(rs,mid+1,r,v); if(v<=mid)res+=qmore(ls,l,mid,v); return res; } int qmore(int x,int v) { int res=0; for(;x>=1;x-=(x&-x)) res+=qmore(rt[x],1,n,v); return res; } int qless(int u,int l,int r,int v) { if(!u) return 0; if(v>r) return tr[ u ].s; int res=0; res+=qless(ls,l,mid,v); if(v>mid) res+=qless(rs,mid+1,r,v); return res; } int qless(int x,int v) { int res=0; for(;x>=1;x-=(x&-x))res+=qless(rt[x],1,n,v); return res; } int main() { scanf("%d%d",&n,&m); memset(rt,0,sizeof(rt)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]);pos[a[i]]=i; ans+=qmore(i-1,a[i]); change(i,a[i],1); } while(m--) { printf("%lld\n",ans); int v;scanf("%d",&v); ans-=qmore(pos[v]-1,v)+qless(n,v)-qless(pos[v]-1,v); change(pos[v],v,-1); } return 0; }
二维线段树（1700ms,超时2个点）:#include<bits/stdc++.h> using namespace std; const int N=1e5+10; #define mid ((l+r)>>1) struct node{int a,b;}a[N]; int n,m,bb[N],bn,pos[N]; int root,totx,xls[N*2],xrs[N*2]; int toty,rt[N*2],yls[N*2*200],yrs[N*2*200],d[N*2*200]; void changeY(int &p,int l,int r,int y,int c) { if(!p)p=++toty; d[p]+=c; if(l==r) return ; if(y<=mid) changeY(yls[p],l,mid,y,c); else changeY(yrs[p],mid+1,r,y,c); } void changeX(int &p,int l,int r,int x,int y,int c) { if(!p)p=++totx; changeY(rt[p],1,bn,y,c); if(l==r) return ; if(x<=mid)changeX(xls[p],l,mid,x,y,c); else changeX(xrs[p],mid+1,r,x,y,c); } int queryY(int p,int l,int r,int y1,int y2) { if(!p) return 0; if(y1<=l && r<=y2) return d[p]; int res=0; if(y1<=mid) res+=queryY(yls[p],l, mid,y1,y2); if(y2 >mid) res+=queryY(yrs[p],mid+1,r,y1,y2); return res; }int queryX(int p,int l,int r,int x1,int x2,int y1,int y2) { if(!p) return 0; if(x1<=l && r<=x2) return queryY(rt[p],1,bn,y1,y2); int res=0; if(x1<=mid) res+=queryX(xls[p],l, mid,x1,x2,y1,y2); if(x2 >mid) res+=queryX(xrs[p],mid+1,r,x1,x2,y1,y2); return res; }
int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i].b),a[i].a=i;
for(int i=1;i<=n;i++) bb[i]=a[i].b; sort(bb+1,bb+n+1);bn=unique(bb+1,bb+1+n)-bb-1; for(int i=1;i<=n;i++){a[i].b=lower_bound(bb+1,bb+bn+1,a[i].b)-bb;pos[a[i].b]=i;} root=totx=toty=0;memset(rt,0,sizeof(rt)); memset(d,0,sizeof(d)); for(int i=1;i<=n;i++)changeX(root,1,n,a[i].a,a[i].b,1); long long ans=0; for(int i=1;i<=n;i++)ans+=queryX(root,1,n,1,a[i].a-1,a[i].b+1,bn); while(m--) { int x;scanf("%d",&x);x=lower_bound(bb+1,bb+bn+1,x)-bb; int i=pos[x]; printf("%lld\n",ans); ans=ans- queryX(root,1,n,1,a[i].a-1,a[i].b+1,bn) - queryX(root,1,n,a[i].a+1,n,1,a[i].b-1); changeX(root,1,n,a[i].a,a[i].b,-1); } return 0;}
</p>
Benny
LV 10
MOD
@ 2026-5-26 21:02:04
- 1
