Comet OJ Contest #8 D 菜菜种菜

题意

给出一个有向图，每次询问一些点，问哪些点无法直接到达该次询问的所有点

题解

思路清奇，还是太菜了Orz，看别人代码懂了
每次的询问是一段标号连续的点，即一个区间 $[l, r]$ 中的点
这是一个关键的信息，必须要用上
考虑一个点能和周围的点共存的范围，首先，肯定不是无限大的，因为它一旦跟自己能到达的点在一起，自己肯定就是非法的了，所以应该用一个区间表示
形象地说，这是一个安全的范围，不能容纳再扩充的点了

考虑点 $x$ 的安全区间 $[l_{x}, r_{x}]$
$l_{x} = m a x {i + 1 ∣ <mtext> </mtext> D i s (x, i) = T r u e <mtext> </mtext> & & <mtext> </mtext> i < x}$
$r_{x} = m i n {i - 1 ∣ <mtext> </mtext> D i s (x, i) = T r u e <mtext> </mtext> & & <mtext> </mtext> i > x}$

当询问的左边界 $L$ 到达 $l_{x}$ 时，右边界 $R$ 落在 $[x, r_{x}]$ 时，点 $x$ 是合法的
所以，每次将这样的区间加对应点的权值，询问时，看位置 $R$ 的值就是答案
左边界右移之前，记得将当前点的对应区间恢复，因为以后再也不会统计到它了

代码

#include<bits/stdc++.h>
#define N 1000010
#define INF 0x3f3f3f3f
#define eps 1e-4
#define pi 3.141592653589793
#define mod 998244353
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef pair<int,int> pp;

namespace IO{ 
    #define BUF_SIZE 100000 
    #define OUT_SIZE 100000 
    #define ll long long 
    //fread->read 
    bool IOerror=0; 
    inline char nc(){ 
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; 
        if (p1==pend){ 
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); 
            if (pend==p1){IOerror=1;return -1;} 
        } 
        return *p1++; 
    } 
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';} 
    inline void read(int &x){ 
        bool sign=0; char ch=nc(); x=0; 
        for (;blank(ch);ch=nc()); 
        if (IOerror)return; 
        if (ch=='-')sign=1,ch=nc(); 
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
        if (sign)x=-x; 
    } 
};
using namespace IO;
struct BIT{
    LL d[N];
    void updata(int x,int y){for(int i=x;i<N;i+=i&-i)d[i]+=y;}
    LL sum(int x){LL res=0;for(int i=x;i;i-=i&-i)res+=d[i];return res;}
}BT;

int l[N],r[N],c[N],ans[N];
vector<pp>G[N];
vector<int> v[N];
int main(){
    int n,m,Q;
    read(n);read(m);read(Q);
    for(int i=1;i<=n;i++) read(c[i]),l[i]=0,r[i]=n+1;
    for(int i=1,x,y;i<=m;i++){
        read(x);read(y);
        if (y>x) r[x]=min(r[x],y);else
                l[x]=max(l[x],y);
    }
    for(int i=1;i<=n;i++) v[l[i]+1].pb(i);
    for(int i=1;i<=Q;i++){
        int x,y;read(x);read(y);
        G[x].pb(pp(y,i));
    }
    for(int i=1;i<=n;i++){
        for(auto j:v[i]) BT.updata(j,c[j]),BT.updata(r[j],-c[j]);
        for(auto j:G[i]) ans[j.se]=BT.sum(j.fi);
        BT.updata(i,-c[i]);BT.updata(r[i],c[i]);
    }
    LL t=0;
    for(int i=1;i<=Q;i++) t^=1ll*i*ans[i];
    cout<<t;
}