68分求调 Wa #1 #2 #11 #12(悬关)
查看原帖
68分求调 Wa #1 #2 #11 #12(悬关)
704655
CAICAIA楼主2024/8/16 19:12
#include<bits/stdc++.h>
using namespace std;
const int MX=1510000,INF=0x3f3f3f3f;
const int MO=1e9+7;
struct node{
    int lc,rc;
    int lx,rx;
}tree[MX<<1];
int cnt=0,root=0;
long long input_l[MX]={0};
long long input_r[MX]={0};
int pos[MX]={0};
vector<int>vec[MX<<1];
vector<int>vec2[MX<<1];
void build(int &now,int lt,int rt){
    if(!now)  now=++cnt,tree[now].lx=lt,tree[now].rx=rt;
    if(lt==rt){
        pos[lt]=now;
        return ;
    }
    int mid=(lt+rt-1)>>1;
    build(tree[now].lc,lt,mid);build(tree[now].rc,mid+1,rt);
    vec[now].push_back(tree[now].lc);vec[now].push_back(tree[now].rc);
}
void add(int now,int lt,int rt,int l,int r,int x){
    if(lt>r||l>rt)  return ;
    if(l<=lt&&rt<=r){
        vec[x].push_back(now);
        return ;
    }
    int mid=(lt+rt-1)>>1;
    add(tree[now].lc,lt,mid,l,r,x);add(tree[now].rc,mid+1,rt,l,r,x);
    return ;
}
int n,len;
long long xi[MX]={0},ri[MX]={0};
long long mid[MX]={0};
void li(){
    for(int i=1;i<=n;i++)  mid[i]=xi[i];
    for(int i=n+1;i<=n+n;i++)  input_l[i-n]=mid[i]=xi[i-n]-ri[i-n];
    for(int i=n+n+1;i<=n+n+n;i++)  input_r[i-n-n]=mid[i]=xi[i-n-n]+ri[i-n-n];
    sort(mid+1,mid+1+n+n+n);len=unique(mid+1,mid+1+n+n+n)-mid-1;
    for(int i=1;i<=n;i++)   xi[i]=lower_bound(mid+1,mid+len+1,xi[i])-mid;
    for(int i=1;i<=n;i++)   input_l[i]=lower_bound(mid+1,mid+len+1,input_l[i])-mid;
    for(int i=1;i<=n;i++)   input_r[i]=lower_bound(mid+1,mid+len+1,input_r[i])-mid;
}
long long qian[MX]={0};
int tim=0,dfn[MX]={0},low[MX]={0};
int belong[MX]={0},cntn=0;
int dp[MX][2]={0};
bool flag[MX]={0};stack<int>st;
void tarjan(int now){
    dfn[now]=low[now]=++tim;
    st.push(now);flag[now]=1;
    for(auto to:vec[now]){
        if(!dfn[to]){
            tarjan(to);
            low[now]=min(low[now],low[to]);
        }
        else if(flag[to]){
            low[now]=min(low[now],dfn[to]);
        }
    }
    if(dfn[now]==low[now]){
        int x=0;cntn++;
        dp[cntn][0]=INF,dp[cntn][1]=-INF;
        while(x!=now){
            x=st.top();st.pop();flag[x]=0;
            belong[x]=cntn;
            dp[cntn][0]=min(dp[cntn][0],tree[x].lx);
            dp[cntn][1]=max(dp[cntn][1],tree[x].rx);
        }
    }
}
int in[MX]={0};
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld%lld",xi+i,ri+i);
    li();
    for(int i=1;i<=n;i++)  qian[xi[i]]++;
    for(int i=1;i<=len;i++)  qian[i]+=qian[i-1];
    build(root,1,len);
    for(int i=1;i<=n;i++){
        add(root,1,len,input_l[i],input_r[i],pos[xi[i]]);
        // printf("check %d %d %d\n",input_l[i],input_r[i],pos[xi[i]]);
    }
    // for(int i=1;i<=n;i++)  printf("%d ",pos[xi[i]]);printf("-----pos\n");
    // for(int i=1;i<=len;i++)  printf("%d ",mid[i]);printf("-----mid\n");

    // for(int i=1;i<=cnt;i++){
    //     printf("i=%d sum=%d lx=%d rx=%d\n",i,tree[i].sum,tree[i].lx,tree[i].rx);
    // }
    // for(int i=1;i<=cnt;i++){
    //     for(auto j:vec[i])  printf("%d %d\n",i,j);
    // }
    for(int i=1;i<=cnt;i++){
        if(!dfn[i])  tarjan(i);
    }
    for(int i=1;i<=cnt;i++){
        for(auto j:vec[i])if(belong[i]!=belong[j])  vec2[belong[j]].push_back(belong[i]),in[belong[i]]++;
    }
    // for(int i=1;i<=cntn;i++){
    //     for(auto j:vec2[i])  printf("%d %d\n",i,j);
    // }
    queue<int>qu;
    for(int i=1;i<=cntn;i++)if(!in[i])qu.push(i);
    while(!qu.empty()){
        int now=qu.front();qu.pop();
        for(auto to:vec2[now]){
            dp[to][0]=min(dp[to][0],dp[now][0]);
            dp[to][1]=max(dp[to][1],dp[now][1]);
            if(!--in[to])qu.push(to);
        }
    }
    long long sum=0;
    for(long long i=1;i<=n;i++){
        long long x=qian[dp[belong[pos[xi[i]]]][1]]-qian[dp[belong[pos[xi[i]]]][0]-1];
        // printf("check %d l=%d r=%d\n",x,dp[belong[pos[xi[i]]]][0],dp[belong[pos[xi[i]]]][1]);
        sum=(sum+(x*i)%MO)%MO;
    }
    printf("%lld",sum);
    return 0;
}//P5025

思路是线段树建图,缩点后dp,记录区间开始和结束的位置,前缀和求区间和

2024/8/16 19:12
加载中...