源代码
// LUOGU_RID: 116328195
//#pragma GCC optimize(2)
#include<cstdio>
#include<vector>
#define lol long long
const int N=2e5+1;
const int mod=998244353;
lol Inv(lol x,int y=mod-2)
{
lol ans = 1;
while (y)
{
if (y & 1) ans = 1ll * ans * x % mod;
x = 1ll * x * x % mod;
y >>= 1;
}
return ans;
}
lowbit(int x){return x&-x;}
struct BIT
{
std::vector<int>idx;
void update(int i,int k)//单点修改
{
for(;i<=N;i+=lowbit(i))
{
idx[i]+=k%mod;
idx[i]%=mod;
}
}
int query(int i)
{
int ans1=0;
for(;i>0;i-=lowbit(i))
ans1=(ans1+idx[i])%mod;
return ans1;
}
BIT()
{
idx.reserve(N+5);
}
};
int main()
{
BIT _cont/*小于某个权值的球的数量*/,_sum/*总和*/;
int n;
long long ans=0,sum2=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int zzz;
scanf("%d",&zzz);
ans+=(((lol)_cont.query(zzz)*2ll+1ll)*(lol)zzz)%(lol)mod;
ans%=(lol)mod;/*比它权值小或等于的数*//*只算一次自己*//*权值*/
ans+=(sum2-(lol)_sum.query(zzz))*2ll%(lol)mod;
ans%=(lol)mod;/*比它权值大的数的权值总和*/
printf("%lld\n",(lol)ans*Inv((lol)i*(lol)i%(lol)mod)%(lol)mod);
sum2=(zzz+sum2)%mod;
_cont.update(zzz,1);
_sum.update(zzz,zzz);
}
return 0;
}
ATCoder上的错误
./Main.cpp:19:13: error: ISO C++ forbids declaration of ‘lowbit’ with no type [-fpermissive]
19 | lowbit(int x){return x&-x;}
| ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:48:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
48 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
./Main.cpp:52:14: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
52 | scanf("%d",&zzz);
| ~~~~~^~~~~~~~~~~
本地 devc++ 返回的编译结果
编译结果...
--------
- 错误: 0
- 警告: 0
- 输出文件名: C:\Users\Administrator\Documents\ABC276F.exe
- 输出大小: 1.61208152770996 MiB
- 编译时间: 0.52s