NOIP模拟题 2015.8.10 T3
BZOJ 1095

NOIP模拟题 2015.8.16 T3

HJWJBSR posted @ 2015年8月19日 18:58 in 题解 , 436 阅读

题解:考场上面肉眼感觉这题可以用线段树或者平衡树,但是很关键的问题就是打标记怎么打,我还naive以为这里的T2车跟一般的修改标记没什么很大区别,一般都可以先修改后加减,修改的时候把子树的加减标记也同时改变就不会有问题。但是这里的仔细想想两个操作都是会互相造成影响的,按上面那样打标记是会出现问题的。不过由于输出只有一个数并且数据还是比较良心还算骗到了50分。比暴力还是好点。后来看题解好像要用分块,并且在块上打了四个标记,标程也非常蛋疼,反正并没有看懂= =。而且题解里面还抽逼说什么维护的东西太多线段树是打不了这个的标记的,但是其实线段树平衡树相关还是可以维护这些的。维护的标记不变,但是顺序改为一个节点先下传加减再修改,下传加减的时候把子树的修改加减标记同时修改就可以了,脑补感觉是对的(你是想在我的博客里面找证明这种东西么【斜眼*ei】),而且也过了这道题= =

我是用splay写的,反正每次就暴力找已经废掉的节点删掉,这是n log n的,不过貌似线段树写也差不多的样子,但是好像由于不能删节点好像还要多打点标记的说

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 200050
#define INF 0x7f7f7f7f
#define m3(x,y,z) min(min(x,y),z)
int c[N][2],fa[N],gf,mi[N],ad[N],xg[N],n,m;
int t[N],sum[N],li[N],ri,ans=0;
inline int Read()
 {
	 int x=0;char y;
	 do y=getchar(); while (y<'0'||y>'9');
	 do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
	 return x;
 }
inline void Update(int x)
 {
 	mi[x]=m3(t[x],mi[c[x][0]],mi[c[x][1]]);
 	sum[x]=sum[c[x][0]]+sum[c[x][1]]+1;
 }
int Set_up(int x,int y)
 {
	 if (x>y) return 0;
	 int i=x + y >> 1,j=!i?n+2:i;
	 mi[j]=t[j];sum[j]=1;
	 if (x==y) return j;
     c[j][0]=Set_up(x,i-1);c[j][1]=Set_up(i+1,y);
	 fa[c[j][0]]=j;fa[c[j][1]]=j;
	 Update(j);return j;
 }
inline void xgj(int x)
 {
	 if (!x||!xg[x]) return;
	 t[x]=max(t[x],xg[x]);xg[c[x][0]]=max(xg[c[x][0]],xg[x]);
	 xg[c[x][1]]=max(xg[c[x][1]],xg[x]);
	 mi[x]=max(mi[x],xg[x]);xg[x]=0;
 }
inline void adj(int x)
 {
 	 if (xg[c[x][0]]) xg[c[x][0]]+=ad[x];
 	 if (xg[c[x][1]]) xg[c[x][1]]+=ad[x];
	 if (!x||!ad[x]) return;
	 t[x]+=ad[x];ad[c[x][0]]+=ad[x];ad[c[x][1]]+=ad[x];
	 mi[x]+=ad[x];ad[x]=0;
 }
void Rotate(int x)
 {
	 int i=fa[x],j=fa[i],k=c[i][0]==x;
	 if (j) c[j][c[j][1]==i]=x;else gf=x;
	 if (c[x][k]) fa[c[x][k]]=i;
	 c[i][!k]=c[x][k];fa[i]=x;
	 c[x][k]=i;fa[x]=j;
	 Update(i);
	 return;
 }
inline void Down(int x)
 {adj(x);xgj(x);}
void Up(int x)
 {if (fa[x]) Up(fa[x]);Down(x);Down(c[x][0]);Down(c[x][1]);}
void Splay(int x)
 {
	Up(x);
	while (fa[x])
	 {
		if (fa[fa[x]])
		 Rotate(c[fa[fa[x]]][0]==fa[x]^c[fa[x]][0]==x?x:fa[x]);
		Rotate(x);
	 }
	Update(x);
	return;
 }
int Fdown(int x,int y)
 {
	 if (!x) return 0;int k;
	 if (x==n+2||x<y) {k=Fdown(c[x][1],y);return k?k:x;}
	   else return Fdown(c[x][0],y);
 }
int Fup(int x,int y)
 {
	 if (!x) return 0;int k;
	 if (x!=n+2&&x>y) {k=Fup(c[x][0],y);return k?k:x;}
	   else return Fup(c[x][1],y);
 }
void Form(int x,int y)
 {
	 int k=Fdown(gf,x),l=Fup(gf,y);
	 Splay(l);fa[c[l][0]]=0;
	 Splay(k);Update(gf=fa[c[l][0]=k]=l);
 }
void FIT(int x)
 {
	 Down(x);
	 if (mi[x]>0) return;
     if (t[x]<=0) li[++ri]=x;
	 FIT(c[x][0]);FIT(c[x][1]);
 }
inline int Delete(int x)
 {
	 while (c[x][0]||c[x][1]) Rotate(c[x][0]?c[x][0]:c[x][1]);
	 c[fa[x]][c[fa[x]][1]==x]=0;return fa[x];
 }
void up(int x)
 {
	 Down(c[x][0]);Down(c[x][1]);Update(x);
	 if (fa[x]) up(fa[x]);
 }
int main()
 {
	 freopen("road.in","r",stdin);freopen("road.out","w",stdout);
	 n=Read();m=Read();
	 for (int k=Read(),i=1;i<=n;i++) t[i]=k;mi[0]=INF;
	 gf=Set_up(0,n+1);fa[0]=c[0][0]=c[0][1]=0;
	 while (m--)
	  {
		  int k=Read(),q=Read(),w=Read(),e=Read();
	      if (k==1)
		   {
			   Form(q,w);
			   if (sum[c[c[gf][0]][1]]!=w-q+1) continue;
			   ad[c[c[gf][0]][1]]=-e;adj(c[c[gf][0]][1]);
			   if (mi[c[c[gf][0]][1]]<=0) FIT(c[c[gf][0]][1]);
			   Update(c[gf][0]);Update(gf);ans++;
			   while (ri--) up(Delete(li[ri+1]));ri++;
		   } else
		  if (k==2)
		   {
			   Form(q,w);
			   ad[c[c[gf][0]][1]]=e;adj(c[c[gf][0]][1]);
			   Update(c[gf][0]);Update(gf);
		   } else
		   {
			   Form(q,w);
			   xg[c[c[gf][0]][1]]=e;xgj(c[c[gf][0]][1]);
			   Update(c[gf][0]);Update(gf);
		   }
	  }
	 cout <<ans<<endl;
	 return 0;
 }

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter