[Comet OJ Contest 8][二维数点+扫描线]菜菜种菜

题面

[题目描述]

菜菜太菜，但他不想种菜。
有 $n$ 块土地，每块土地有一个菜值。它们之间有 $m$ 条小路，每条连接两块土地，小路只能单向通行，不存在一条小路两端连接同一块土地，但可能存在两条小路两端连接的土地分别相同。如果存在一条从土地 $u$ 到土地 $v$ 的小路，则称 $u$ 能直接到达 $v$。
菜菜可以购买一些土地，他必须在其中选择一块建造自己的家，所购买的剩下的土地都被作为菜地。因为菜菜不想种菜，所以他希望从他家能直接到达的土地中，一块菜地也没有（如果菜菜家不能直接到达任何一块土地，这也能满足他的愿望）。
菜菜提出了 $q$ 个问题，每个问题给出$L$,$R$，询问如果他购买了第 $L$ 到第 $R$ 块之间的所有土地，那么所有满足他愿望的建造家的选址的菜值之和是多少？

注意，本题空间限制为128MB

[输入格式]

第 $1$ 行 $3$ 个由空格隔开的整数 $n$,$m$,$q$ ，分别表示土地的块数、小路的条数和问题的个数。
第 $2$ 行 $n$ 个由空格隔开的整数，第 $i$ 个数 $a_i$表示第 $i$ 块土地的菜值。
接下来$m$ 行，每行$2$ 个由空格隔开整数 $u_i,v_i$，表示第$i$ 条小路从第 $u_i$块土地通向第 $v_i$块土地。
接下来 $q$ 行，每行 $2$ 个由空格隔开整数 $l_i$,$r_i$，表示菜菜第 i 个问题中购买了 $[l_i,r_i]$中的所有土地。
$1\le n,m,q\le 10^6$
$1\le a_i\le 300$
$1\le u_i,v_i\le n,u_i?=v_i$
$1\le l_i\le r_i\le n$。

[输出格式]

为了避免输出量过大，设 $an{s}_i$表示第 $i$ 个询问的答案。你只需要输出1行1个整数 ${\mathrm{x}\mathrm{o}\mathrm{r}}_{i=1}^{q}i\times an{s}_i$，即所有询问的编号与答案的乘积依次按位异或 （c++中的64位整数^）的结果。

[样例1输入]

4 2 2
3 5 10 6
1 4
2 3
2 3
1 3

[样例1输出]

16

[样例2输入]

5 6 3
114 29 219 231 165
5 4
1 2
1 3
5 3
3 2
3 4
2 2
1 2
4 5

[样例2输出]

658

题解

转化问题

首先我们考虑最暴力的做法,我们可以枚举$?x,x\in [L,R]$中的所有$x$，我们只需要检验这个$x$是否合法即可。
一个点$x$合法，当且仅当不存在$y\in [L,R]$使得$x,y$之间有一条连边。
注意到我们的询问是一个区间，我们可以发现如果区间包含了能够被$x$到达的编号小于$x$且与$x$差距最小的点和编号大于$x$且与$x$差距最小的点这两个点的任何一个点，那么这个点就不合法，反之，当前的$x$就合法。
因此定义$pr{e}_x$为编号小于$x$且与$x$差距最小的点,$nx{t}_x$为编号大于$x$且与$x$差距最小的点，如果只要以下条件$x$就合法:
$$pr{e}_x<L\le x且x\le R<nx{t}_x$$
然后套路就来了,我们将区间看做一个点$(L,R)$,将$x$看做$(pr{e}_x+1,x,x,nx{t}_x?1)$(对应$(x_0,y_0,x_1,y_1)$)的一个矩形。
因此问题就转化为:统计一个点$(L,R)$被多少个矩形包围。

扫描线

考虑使用扫描线来解决这个问题。
我们将矩阵拆为$(x_0,y_0,y_1),(x_1+1,y_0,y_1)$两条与y轴平行的直线，将点与直线混在一起按x轴排序。
维护一个可以区间加减的数据结构，在第一条直线时往区间$(y_0,y_1)$加1，在第二条直线时往区间$(y_0,y_1)$减1。
对于每个询问，我们只需要单点查询当前数据结构中$x$点的值即可。
我们用数状数组就能够完成这个工作。
时间复杂度:$O(n\log n)$

实现

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define MAXN 1000002
#define MAXM 3000002
#define LL long long
int n,m,q,cnt,sum;
int val[MAXN+5],ans[MAXN+5],C[MAXN+5];
int Cl[MAXN+5],Cr[MAXN+5];
LL T;
struct point{
    int kdf,x,l,r,val;
}p[MAXM+5];
int read(){
    int x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=x*10+c-'0';c=getchar();}return x*F;
}
int lowbit(int x){
    return x&(-x);}
bool cmp(point s1,point s2){
    if(s1.x==s2.x)return s1.kdf>s2.kdf;return s1.x<s2.x;
}
void Insert(int x,int val){
    while(x>0){
    C[x]+=val;x-=lowbit(x);}
}
int Query(int x){
    int res=0;while(x<=MAXN){
    res+=C[x];x+=lowbit(x);}return res;
}
int main(){
    n=read(),m=read(),q=read();for(int i=1;i<=n;i++){
    val[i]=read();Cl[i]=0;Cr[i]=n+1;}for(int i=1;i<=m;i++){
    int u=read(),v=read();if(v<u)Cl[u]=max(Cl[u],v);if(v>u)Cr[u]=min(Cr[u],v);}for(int i=1;i<=q;i++){
    int l=read(),r=read();p[++cnt]=(point){
    0,l,r,0,i};}for(int i=1;i<=n;i++){
    p[++cnt]=(point){
    1,Cl[i]+1,i,Cr[i]-1,val[i]};p[++cnt]=(point){
    1,i+1,i,Cr[i]-1,-val[i]};}sort(p+1,p+cnt+1,cmp);for(int i=1;i<=cnt;i++){
    if(!p[i].kdf){
    ans[p[i].val]=Query(p[i].l);}else{
    Insert(p[i].r,p[i].val);if(p[i].l>1)Insert(p[i].l-1,-p[i].val);}}for(int i=1;i<=q;i++)T^=(1LL*i*ans[i]);printf("%lld",T);
}