蛋蛋与北大信科
| 总时限 | 10s | 内存限制 | 256MB |
|---|---|---|---|
| 出题人 | lydrainbowcat | 提交情况 | 1/25 |
背景
琰琰（孩纸们读作：蛋蛋）是妙峰书苑的一名萌萌哒教师，她的夫君（孩纸们称之为：北大信科）是北京大学信息科学技术学院的毕业生。无聊之余，蛋蛋与北大信科就成了孩纸们调侃的对象。
描述
宝哥和宝妹是孩纸们当中一对恩爱的兄妹。有一天，宝哥送给宝妹一本名叫《蛋蛋与北大信科传》的小说，对这本书爱不释手的宝妹每天晚上都会读上几页。但是宝妹读书的方法非常特别。
《蛋蛋与北大信科传》一共M页，起初所有页都是没有标记的。第i天读书时，宝妹会手持一根颜色为i的水彩笔，并把这一天读过的页标记为颜色i。她每天选择一个区间[L,R]，阅读在[L,R]中所有从未读过（没有标记）的页，以及[L,R]中所有与第L页上的标记颜色相同的页。读过的这些页会被重新标记颜色（颜色可以覆盖）。N天之后，宝妹想知道她一共读过了多少页书呢？
输入格式
第一行两个整数M、N。
接下来N行，每行两个整数L、R。第i+1行的两个数表示宝妹第i天选择的区间。
输出格式
一个整数，表示宝妹一共读了多少页书。
样例输入
15 5 1 6 4 8 2 7 10 12 7 13
样例输出
20
数据范围与约定
- 对于20%的数据，1<=n,m<=1000。
- 对于50%的数据，1<=n<=1000，1<=m<=100000。
- 对于100%的数据，1<=n,m<=300000，1<=L<=R<=m。
样例解释
第一天宝妹读1~6页，标记上颜色1。第二天读4~8页，其中56和4颜色相同均为1，78未被标记，4~8读完后标记上颜色2。第三天读23两页，因为2~7中都有标记且只有3和2颜色一样，读完后2~3标记颜色为3。第四天读10~12页，标记上颜色4。第五天读789、13页，13页没有标记，89也和7页的颜色相同，读完后789、13标记颜色5。一共读了6+5+2+3+4=20页书。
上面丧心病狂
本题，建n棵Splay，每种颜色一棵
1.记得将2棵子树裁下（是裁下，不是取出所有结点），启发式合并。
2.记得记录某个结点所在子树（Important）
D了一天Bug就是上面那条导致我T
后来改成裁又WA（没用修改结点所在子树）
后来找lyd的标程看——原来只要记录根所在子树（智商拙计）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
#define F (1000000009)
#define MAXN (900000+10)
#define MAXM (900000+10)
typedef long long ll;
struct node
{
int ch[2],siz,c,fa,no;
node():siz(0),c(0),fa(0),no(0){ch[0]=ch[1]=0;}
node(int _c):siz(1),c(_c),fa(0),no(0){ch[0]=ch[1]=0;}
node(int _c,int _fa):siz(1),c(_c),fa(_fa),no(0){ch[0]=ch[1]=0;}
void clear(int _no){siz=1,fa=0,no=_no,ch[0]=ch[1]=0;}
}a[MAXN];
int root[MAXM]={0}; //<-is color
void update(int x){ a[x].siz=a[a[x].ch[0]].siz+a[a[x].ch[1]].siz+1; }
void rotate(int x) //assume x has father
{
int y=a[x].fa,z=a[y].fa;
int p=a[x].c<a[y].c;
if (z)
if (a[z].ch[0]==y) a[z].ch[0]=x;else a[z].ch[1]=x;
a[y].ch[p^1]=a[x].ch[p];
if (a[y].ch[p^1]) a[a[y].ch[p^1]].fa=y;
a[x].ch[p]=y;
a[y].fa=x,a[x].fa=z;
update(y);
}
void splay(int x,int p) //let x rotate to p
{
while (a[x].fa!=p)
{
int y=a[x].fa,z=a[y].fa;
if (z!=p)
if ((a[y].ch[0]==x)^(a[z].ch[0]==y)) rotate(x);else rotate(y);
rotate(x);
}
update(x);
}
void insert(int &x,int p)
{
if (!x) {x=p;return;}
bool p2=a[x].c<a[p].c;
insert(a[x].ch[p2],p);a[a[x].ch[p2]].fa=x;
update(x);
}
int find(int x,int c)
{
if (!x) return 0;
if (c==a[x].c) return x;
bool p=a[x].c<c;
int k=find(a[x].ch[p],c);
if (k) return k;
if (a[x].c<c) return x;
return 0;
}
int find2(int x,int c)
{
if (!x) return 0;
if (c==a[x].c) return x;
bool p=a[x].c<c;
int k=find2(a[x].ch[p],c);
if (k) return k;
if (a[x].c>c) return x;
return 0;
}
int q[MAXN],tot=0;
void bfs(int x)
{
if (!x) return ;
bfs(a[x].ch[0]);
q[++tot]=x;
bfs(a[x].ch[1]);
}
void merge(int &x,int new_num)
{
ForD(i,tot)
{
int now=q[i];
a[now].clear(new_num);
insert(x,now);
splay(now,0);
x=now;
}
}
int n,m;
int where[MAXN];
void print(int x)
{
if (!x) return ;
print(a[x].ch[0]);
cout<<a[x].c<<' ';
print(a[x].ch[1]);
}
int make_q(int x,int l,int r,bool is_y) //第x棵子树 [l,r]之间的加入q
{
int x1=find(root[x],l-1),x2=find2(root[x],r+1);
splay(x1,0);
root[x]=x1;where[x1]=x;
splay(x2,x1);
if (is_y)
{
bfs(a[x2].ch[0]);
a[x2].ch[0]=0;update(x2);update(x1);
return 0;
}
else
{
int k=a[x2].ch[0];a[k].fa=a[x2].ch[0]=0;
update(x2);update(x1);
return k;
}
}
void build(int &x,int l,int r)
{
int m=l+r>>1;
x=m;
if (l<m) build(a[x].ch[0],l,m-1),a[a[x].ch[0]].fa=x;
if (m<r) build(a[x].ch[1],m+1,r),a[a[x].ch[1]].fa=x;
update(x);
}
int getroot(int x)
{
while (a[x].fa) x=a[x].fa;
return x;
}
int main()
{
// freopen("book.in","r",stdin);
scanf("%d%d",&n,&m);
For(i,n) a[i].c=i,a[i].siz=1;
a[n+1].c=0,a[n+1].siz=1;a[n+2].c=n+1,a[n+2].siz=1;
build(root[0],1,n);
insert(root[0],n+1),insert(root[0],n+2);
where[root[0]]=0;
ll ans=0;
For(i,m)
{
// print(root[1]);cout<<endl;
int l,r;
scanf("%d%d",&l,&r);
int f=where[getroot(l)];
tot=0;
make_q(0,l,r,1);root[i]=make_q(f,l,r,0);
merge(root[i],i);
// cout<<a[root[i]].siz<<endl;
ans+=a[root[i]].siz;
a[n+2+i]=node(0);a[n+2+i].no=i,a[n+2+m+i]=node(n+1),a[n+2+m+i].no=i;
insert(root[i],n+2+i),insert(root[i],n+2+m+i);
where[root[i]]=i;
}
cout<<ans<<endl;
// while(1);
return 0;
}