Atcoder 221

\(D.Online games\)

题意:有\(n\)个玩家，每个玩家有一个登录开始时间\(A[i]\)和持续时间\(B[i]\),也就是说玩家\(i\)会在第\(A[i],A[i+1]...A[i+1]+B[i]-1\)天登录，求有\(1,2,3...n\)个人登录的天数

Sol：类似于扫描线的思想，把开始时间\(A[i]\)标记为1，结束时间\(A[i]+B[i]-1\)标记为-1,然后对所有的\(2*n\)个区间从小到大排序遍历即可

时间复杂度\(O(nlogn)\)

#include 
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
int ans[N];
vector>v;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int a,b;
		cin>>a>>b;
		v.pb({a,1});
		v.pb({a+b,-1});
	}
	sort(v.begin(),v.end());
	int cnt=0;
	for(int i=0;i


$E - LEQ $
题意:给定一个序列\(A=(A_1,A_2,...,A_n)\),长度为\(N\)。定义\(A^{'}=(A_1^{'},A_2^{'},...,A_k^{'})\)，满足\(A^{'}\)为\(A\)的子序列，长度至少为2，且\(A_1^{'}\le A_k^{'}\) ,求这样的子序列的个数,由于答案可能很大，所以答案对\(998244353\)取模
数据范围:\(2\le N\le 3\times 10^5\)             \(1\le A_i \le 10^9\)
Sol:暴力做法很显然就是对任意的一对\(A_i\le A_j(i,对答案的贡献就是\(2^{j-i-1}\),但这样的复杂度是\(O(n^2)\)。考虑优化时间复杂度到\(O(nlogn)\),注意到$2^{j-i-1} $  = \(\frac{2^{j-1}}{2^i}\) ，于是对于每个\(j\)，我们可以统计\(\sum_{i=1\ and\ A_i\le A_j}^{j-1}\frac{1}{2^{i}}\) ,由于\(A_i\)比较大，所以先将\(A_i\)离散化，然后按照树状数组求逆序对的思路我们来求顺序对，\(add\)操作的时候每次在相应位置上加上\(\frac{1}{2^{i}}\)即可
#include 
#define ll long long
using namespace std;
const int N=3e5+10;
const int mod= 998244353;
int m;
int a[N];
vectorv;
ll qmi(ll x,ll y)
{
	ll res=1;
	while(y)
	{
		if(y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
ll tr[N];
int lowbit(int x){return x&-x;}
void add(int p,ll x)
{
	p++;
   for(;p<=m;p+=lowbit(p))
   	tr[p]=(tr[p]+x)%mod;
}
ll ask(int p)
{
	p++;
	ll res=0;
	for(;p>0;p-=lowbit(p))
	res=(res+tr[p])%mod;
    return res;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll inv=qmi(2,mod-2);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],v.push_back(a[i]);
	sort(v.begin(),v.end());
    m=v.size();
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=n;i++)
    a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin();
 
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
    	ans=(ans+ask(a[i])*qmi(2,i-1))%mod;
        add(a[i],qmi(inv,i));
    }
    cout<

Atcoder 221

Atcoder 221

相关

标签