2 条题解

  • 0
    @ 2026-8-25 10:52:08

    树状数组打错了还有救吗?

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int N=2e5+10;
    struct BIT
    {
    	int c[N],n;
    	void add(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
    	int get(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
    }tr;
    int a[N],b[N],blen,ans[N],n,m,B,sum,len;
    struct node{int l,r,id;}q[N];
    bool cmp(node n1,node n2){return n1.l/B!=n2.l/B?n1.l<n2.l:(n1.l/B)&1?n1.r<n2.r:n1.r>n2.r;}
    void add(int x,int op)
    {
    	int s=op?tr.get(x-1):len-tr.get(x);
    	len++,sum+=s;tr.add(x,1);
    }
    void del(int x,int op)
    {
    	int s=op?tr.get(x-1):len-tr.get(x);
    	len--,sum-=s;tr.add(x,-1);
    }
    signed main()
    {
    	cin>>n>>m;B=sqrt(n);
    	for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
    	sort(b+1,b+n+1);blen=unique(b+1,b+n+1)-b-1;tr.n=blen;
    	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+blen+1,a[i])-b;
    	for(int i=1;i<=m;i++)cin>>q[i].l>>q[i].r,q[i].id=i;
    	sort(q+1,q+m+1,cmp);
    	for(int i=1,l=1,r=0;i<=m;i++)
    	{
    		while(l>q[i].l)add(a[--l],1);
    		while(r<q[i].r)add(a[++r],0);
    		while(l<q[i].l)del(a[l++],1);
    		while(r>q[i].r)del(a[r--],0);
    		ans[q[i].id]=sum;
    	}
    	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
    	return 0;
    }

    【莫队】区间逆序对数[Ynoi2019 模拟赛] Yuno loves sqrt technology II

    信息

    ID
    483
    时间
    10000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    7
    已通过
    3
    上传者