WA 90分求助
查看原帖
WA 90分求助
476767
羊叫兽同学楼主2022/8/5 20:02

rt,

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#define int long long
using namespace std;
int n,m,s,l,i,j,ask[2][114514],zip[114514],top,ans,cnt,qwq[114514],a[114514],sum[114514];
map<int,int>ls;
map<int,bool>askbook;
map<int,bool>book;
bool gui[114514];
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int k)
{
    for(;x<=top;x+=lowbit(x))
        sum[x]+=k;
    return ;
}
int ask_(int x)
{
    int ans=0;
    for(;x>=1;x-=lowbit(x))
        ans+=sum[x];
    return ans;
}
void add_(int x)
{
    if(x<=0||book[x])
        return ;
    top++;
    qwq[top]=x;
    book[x]=true;
}
signed main()
{
    scanf("%lld",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lld%lld",&ask[0][i],&ask[1][i]);
        add_(ask[0][i]);
        add_(ask[0][i]-1);
        add_(ask[0][i]+1);
        add_(ask[1][i]);
        add_(ask[1][i]-1);
        add_(ask[1][i]+1);
        askbook[ask[0][i]]=askbook[ask[1][i]]=true;
    }
    sort(qwq+1,qwq+1+top);
    for(i=1;i<=top;i++)
    {
        ls[qwq[i]]=i;
        zip[i]=1;
        if(!gui[i]&&!askbook[qwq[i]]&&i!=top&&!askbook[qwq[i+1]])
        {
            zip[i]=qwq[i+1]-qwq[i]+1;
            gui[i+1]=true;
        }
    }
    for(i=1;i<=n;i++)
        swap(qwq[ls[ask[0][i]]],qwq[ls[ask[1][i]]]);
    for(i=top;i>=1;i--)
    {
        if(gui[i])
            continue;
        ans+=zip[i]*ask_(ls[qwq[i]]-1);
        add(ls[qwq[i]],zip[i]);
    }
    cout<<ans;
}
2022/8/5 20:02
加载中...