题面
[题目描述]
菜菜太菜，但他不想种菜。
有 nnn 块土地，每块土地有一个菜值。它们之间有 mmm 条小路，每条连接两块土地，小路只能单向通行，不存在一条小路两端连接同一块土地，但可能存在两条小路两端连接的土地分别相同。如果存在一条从土地 uuu 到土地 vvv 的小路，则称 uuu 能直接到达 vvv。
菜菜可以购买一些土地，他必须在其中选择一块建造自己的家，所购买的剩下的土地都被作为菜地。因为菜菜不想种菜，所以他希望从他家能直接到达的土地中，一块菜地也没有（如果菜菜家不能直接到达任何一块土地，这也能满足他的愿望）。
菜菜提出了 qqq 个问题，每个问题给出LLL,RRR，询问如果他购买了第 LLL 到第 RRR 块之间的所有土地，那么所有满足他愿望的建造家的选址的菜值之和是多少？
注意，本题空间限制为128MB
[输入格式]
第 111 行 333 个由空格隔开的整数 nnn,mmm,qqq ，分别表示土地的块数、小路的条数和问题的个数。
第 222 行 nnn 个由空格隔开的整数，第 iii 个数 aia_iai?表示第 iii 块土地的菜值。
接下来mmm 行，每行222 个由空格隔开整数 ui,viu_i,v_iui?,vi?，表示第iii 条小路从第 uiu_iui?块土地通向第 viv_ivi?块土地。
接下来 qqq 行，每行 222 个由空格隔开整数 lil_ili?,rir_iri?，表示菜菜第 i 个问题中购买了 [li,ri][l_i,r_i][li?,ri?]中的所有土地。
1≤n,m,q≤1061\le n,m,q \le 10^61≤n,m,q≤106
1≤ai≤3001\le a_i\le 3001≤ai?≤300
1≤ui,vi≤n,ui≠vi1\le u_i,v_i\le n,u_i\neq v_i1≤ui?,vi?≤n,ui??=vi?
1≤li≤ri≤n1\le l_i\le r_i\le n1≤li?≤ri?≤n。
[输出格式]
为了避免输出量过大，设 ansians_iansi?表示第 iii 个询问的答案。你只需要输出1行1个整数 xori=1qi×ansi{\rm xor}_{i=1}^qi\times ans_ixori=1q?i×ansi?，即所有询问的编号与答案的乘积依次按位异或 （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∈[L,R]\forall x,x\in [L,R]?x,x∈[L,R]中的所有xxx，我们只需要检验这个xxx是否合法即可。
一个点xxx合法，当且仅当不存在y∈[L,R]y\in [L,R]y∈[L,R]使得x,yx,yx,y之间有一条连边。
注意到我们的询问是一个区间，我们可以发现如果区间包含了能够被xxx到达的编号小于xxx且与xxx差距最小的点和编号大于xxx且与xxx差距最小的点这两个点的任何一个点，那么这个点就不合法，反之，当前的xxx就合法。
因此定义prexpre_xprex?为编号小于xxx且与xxx差距最小的点,nxtxnxt_xnxtx?为编号大于xxx且与xxx差距最小的点，如果只要以下条件xxx就合法:
prex<L≤x且x≤R<nxtxpre_x<L≤x且x≤R<nxt_x prex?<L≤x且x≤R<nxtx?
然后套路就来了,我们将区间看做一个点(L,R)(L,R)(L,R),将xxx看做(prex+1,x,x,nxtx?1)(pre_x+1,x,x,nxt_x-1)(prex?+1,x,x,nxtx??1)(对应(x0,y0,x1,y1)(x_0,y_0,x_1,y_1)(x0?,y0?,x1?,y1?))的一个矩形。
因此问题就转化为:统计一个点(L,R)(L,R)(L,R)被多少个矩形包围。
扫描线
考虑使用扫描线来解决这个问题。
我们将矩阵拆为(x0,y0,y1),(x1+1,y0,y1)(x_0,y_0,y_1),(x_1+1,y_0,y_1)(x0?,y0?,y1?),(x1?+1,y0?,y1?)两条与y轴平行的直线，将点与直线混在一起按x轴排序。
维护一个可以区间加减的数据结构，在第一条直线时往区间(y0,y1)(y_0,y_1)(y0?,y1?)加1，在第二条直线时往区间(y0,y1)(y_0,y_1)(y0?,y1?)减1。
对于每个询问，我们只需要单点查询当前数据结构中xxx点的值即可。
我们用数状数组就能够完成这个工作。
时间复杂度:O(nlog?n)O(n \log n)O(nlogn)
实现
#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);
}