社区讨论

萌新求助,树状数组wa了70%

P1637三元上升子序列参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mi85zvk9
此快照首次捕获于
2025/11/21 09:11
4 个月前
此快照最后确认于
2025/11/21 09:11
4 个月前
查看原帖
RT,感觉没有问题,还tm不开数据下载,很难受
CPP
#include <bits/stdc++.h>

using namespace std;
#define int long long
int n;
int a[100005];
int b[100005];
int c[100005];
int r[100005];
int LowBit(int x)
{
    return x&(-x);
}
void Add(int x,int d)
{
    while(x<=n)
    {
        c[x]+=d;
        x+=LowBit(x);
    }
}
int Query(int x)
{
    int res=0;
    while(x)
    {
        res+=c[x];
        x-=LowBit(x);
    }
    return res;
}
bool cmp(int x,int y)
{
    return b[x]>b[y];
}

signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&b[i]);
        a[i]=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;++i)
    
    	printf("%lld ",a[i]);
    }
    	printf("%lld",a[i]);
    }
	printf("\n");
	for(int i=n;i>0;--i)
    {
        r[i]=Query(a[i]-1);
        Add(a[i],1);
    }
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;++i)
    {
        ans+=r[i]*(Query(n)-Query(a[i]));
        Add(a[i],1);
    }
    printf("%lld",ans);
    return 0;
} 

回复

1 条回复,欢迎继续交流。

正在加载回复...