NOI2019D2T1弹跳
前天发了篇D1T1的题解，今天我又来了
看完全部题目，T2T3是啥啊，还是回来看T1吧
哈哈哈，又是最短路！
dij的性质就是每个点只会被标记一次，并且权值非负。
这是个很好的性质！就是说，我们dij的时候只要把新增的矩形内没有被标记过的点标记就好了。
转化：每次把一个矩形内的点全部去掉，并赋值。
看到这里，如果你做过线段树的拓展，就很容易想到线段树！
类似线段树题目：bzoj4127 Abs luogu4145 花神游历各国
其实我只是听过二维线段树而已，根本没写过，当场瞎敲一通就过了
dij部分就不多说了，转化后怎么实现？
这里，我们不用考虑树套树，因为直接用二维线段树就行了。
好像很多人都不知道二维线段树？
二维线段树，就是用每个点表示一个正方形，这个正方形还可以分为4个子正方形。（类似二维st表）
我们用sum来表示一个线段树的正方形内剩下没被标记过的点的总数。
我们用递归来标记点，这样当一个正方形内没有未标记的点时就可以剪掉很多枝。
也就是，当递归到sum=0时，直接返回。
如果当前线段树矩形和dij里更新的矩形没有重合部分，也返回。
否则，继续递归四个子矩形。
当矩形缩成一个点时，在dij那边处理，并将sum清零。
回溯时更新sum值，就这么简单。
不过w和h最大都是n，没关系！用动态开点（就是用到一个区间再开一个区间）！
如果用动态开点，初始化就得一个一个城市加入。反正时限2秒，复杂度也对。
好像跑得挺快？虽然我不会算二维的复杂度
代码：
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=7e4+5,MAXM=1.5e5+5;
int n,m,w,h;
struct node{
int x,y;
int h;
int bgnid; //用来输出
}city[MAXN];
inline bool cmp_city(node a,node b){
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
int GetID(int x,int y){ //根据坐标找城市编号（先排好序）
node f;
f.x=x,f.y=y;
int l=1,r=n;
while(l<r){
int mid=l+r>>1;
if(cmp_city(city[mid],f)) l=mid+1;
else r=mid;
}
return r;
}
struct edge{
int t,l1,r1,l2,r2; //存一个矩形
int d;
inline void Init_bgn(){
d=0;
for(int i=1;i<=n;i++)
if(city[i].bgnid==1){
l1=l2=city[i].x;
r1=r2=city[i].y;
return ;
}
}
}ed[MAXM];
int cnte,nx[MAXM];
inline void adde(int &h,int t,int a,int b,int c,int d){
cnte++;
ed[cnte].t=t;
ed[cnte].l1=a;
ed[cnte].l2=b;
ed[cnte].r1=c;
ed[cnte].r2=d;
nx[cnte]=h;
h=cnte;
}
bool operator <(edge a,edge b){
return a.d>b.d; //dij里给优先队列重载
}
int dis[MAXN];
priority_queue<edge> que;
edge hd;
const int SIZ=1e7+5;
int cntseg,c1[SIZ],c2[SIZ],c3[SIZ],c4[SIZ];
#define getc1 c1[k],l1,r1,midx,midy //4个子正方形的宏定义（降低代码量）
#define getc2 c2[k],l1,midy+1,midx+1,r2
#define getc3 c3[k],midx+1,r1,l2,midy
#define getc4 c4[k],midx+1,midy+1,l2,r2
int sum[SIZ];
inline void pushup(int k){
sum[k]=sum[c1[k]]+sum[c2[k]]+sum[c3[k]]+sum[c4[k]]; //标记上传
}
void modify1(int &k,int l1,int r1,int l2,int r2,const node &ct){ //初始化用的函数
if(!k) k=++cntseg;
if(l1==l2&&r1==r2){
sum[k]=1;
return ;
}
int midx=l1+l2>>1,midy=r1+r2>>1;
if(ct.x<=midx){
if(ct.y<=midy) modify1(getc1,ct);
else modify1(getc2,ct);
}
else{
if(ct.y<=midy) modify1(getc3,ct);
else modify1(getc4,ct);
}
pushup(k);
return ;
}
void modify2(int k,int l1,int r1,int l2,int r2,const edge &e){ //dij更新一个矩形内的点
if(l1>e.l2||r1>e.r2||l2<e.l1||r2<e.r1) return ; //没有重合部分
if(!sum[k]) return ;
// printf("mdf2 %d %d %d %d\n",l1,r1,l2,r2);
if(l1==l2&&r1==r2){
//缩成一个点，直接修改dij里面用的优先队列
sum[k]=0;
int p=GetID(l1,r1);
dis[p]=e.d;
for(int i=city[p].h;i;i=nx[i]){
edge t=ed[i];
t.d=e.d+t.t;
que.push(t);
}
return ;
}
int midx=l1+l2>>1,midy=r1+r2>>1;
modify2(getc1,e); //递归4个子正方形
modify2(getc2,e);
modify2(getc3,e);
modify2(getc4,e);
pushup(k);
return ;
}
inline void Print(){//调试用
for(int i=1;i<=n;i++)
printf("u %d dis %d\n",city[i].bgnid,dis[i]);
puts("");
return ;
}
void dij(){
cntseg=1;
int one=1;
for(int i=1;i<=n;i++)
modify1(one,1,1,n,n,city[i]); //线段树初始化
memset(dis,0x3f,sizeof(dis));
// dis[1]=0;
edge bgn;
bgn.Init_bgn();
que.push(bgn);
while(!que.empty()){
edge hd=que.top();
que.pop(); //dij没什么好讲的吧
// printf("Start mdf2 %d %d %d %d dis %d\n",hd.l1,hd.r1,hd.l2,hd.r2,hd.d);
modify2(1,1,1,n,n,hd);
// Print();
}
return ;
}
/*
5 3 5 5
1 1
3 1
4 1
2 2
3 3
1 123 1 5 1 5
1 50 1 5 1 1
3 10 2 2 2 2
*/
int ans[MAXN];
int main(){
// freopen("jump.in","r",stdin);
// freopen("jump.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&w,&h);
for(int i=1;i<=n;i++)
scanf("%d%d",&city[i].x,&city[i].y),city[i].bgnid=i;
for(int i=1;i<=m;i++){
int p,t,a,b,c,d;
scanf("%d%d%d%d%d%d",&p,&t,&a,&b,&c,&d);
adde(city[p].h,t,a,b,c,d);
}
sort(city+1,city+n+1,cmp_city);
dij();
for(int i=1;i<=n;i++)
ans[city[i].bgnid]=dis[i];
for(int i=2;i<=n;i++)
printf("%d\n",ans[i]);
// fclose(stdin);
// fclose(stdout);
return 0;
}总结
轻松水过T1！相比Day1，只花了2h做T1，还能AC，进步真大！
看来，有时候得分与目标是成正比的。Day1老是想打部分分，结果与正解擦边而过。今天想A题，不仅不用管部分分，还节省了时间。
今年NOI，spfa基本死地彻彻底底了，因为dij有一个被OIer们遗忘很久的性质。
一些算法看似浅显，却像海绵一样（大家都知道我想说什么了）
OI里面到底有没有像文化课里的套路，这真是个谜。谁也说不清算法里面有多少性质可以用，谁知道明年会不会考个spfa把dij卡掉呢？其实人家spfa还是有很多性质的（比如说很不稳定）