bzoj2827: 千山鸟飞绝 平衡树 替罪羊树 蜜汁标记
2024-09-28 04:32:36
这道题首先可以看出坐标没有什么意义离散掉就好了。
然后你就会发现你要每次都更改坐标,而一旦更改受影响的是坐标里的所有数,要是一个一个的改,会不可描述。
所以换个视角,我们要找的是某只鸟所到每个坐标时遇到的最屌的鸟和遇到最大的团体,所以我就蒙了,这怎么改,蜜汁啊!
蓝后就到了标记的神奇应用,用标记的下传重开来把每只鸟在每个坐标里所待的那段时间里遇到的收益搞到。
两个标记: Max_army士气最大值 Max_one 团结最大值
每次来了鸟先把那只鸟的威武值更新那个坐标再放他,放完他再打团结值最大值,关键。
最后他走的时候把标记传给他,最最后输出之前先把每个点都更新。
这样就完美了~~~
我是用的替罪羊树来实现的这个蜜汁标记平衡树
#include<cstdio>
#include<cstring>
#include<map>
#include<iostream>
#define MAXN 30005
using namespace std;
typedef double D;
typedef unsigned long long ULL;
typedef long long LL;
const ULL K=233333333333333ULL;
const D a=0.756;
inline int Max(int x,int y)
{
return x>y?x:y;
}
int pos[MAXN];
map<ULL,int>bird;
int Max_army[MAXN],Max_one[MAXN],n,t,w[MAXN],sz;
inline ULL hash(int x,int y)
{
if(x>=&&y>=)
return (ULL)(x*K+y);
if(x>=&&y<)
{
y=-y;
return (ULL)(x*K-y);
}
if(x<&&y>=)
{
x=-x;
return (ULL)(y-x*K);
}
if(x<&&y<)
{
x=-x;
y=-y;
return (ULL)(-y-K*x);
}
}
struct ScapeGoat_Tree
{
ScapeGoat_Tree *ch[];
int size,key,cover,ex,num,max_army,max_one;
bool bad()
{
return cover*a+<ch[]->cover||cover*a+<ch[]->cover;
}
void pushup()
{
size=ch[]->size+ch[]->size+ex;
cover=ch[]->cover+ch[]->cover+;
}
}pool[MAXN<<],*null,*stack[MAXN<<],*lst[MAXN<<],*root[MAXN<<];
int top,len;
inline void pushdown(ScapeGoat_Tree *p)
{
if(p->ex)
{
Max_one[p->num]=Max(Max_one[p->num],p->max_one);
Max_army[p->num]=Max(Max_army[p->num],p->max_army);
}
if(p->max_one)
{
if(p->ch[]!=null)
p->ch[]->max_one=Max(p->ch[]->max_one,p->max_one);
if(p->ch[]!=null)
p->ch[]->max_one=Max(p->ch[]->max_one,p->max_one);
p->max_one=;
}
if(p->max_army)
{
if(p->ch[]!=null)
p->ch[]->max_army=max(p->ch[]->max_army,p->max_army);
if(p->ch[]!=null)
p->ch[]->max_army=max(p->ch[]->max_army,p->max_army);
p->max_army=;
}
}
inline void Init()
{
null=pool;
null->size=null->key=null->ex=null->cover=null->num=null->max_army=null->max_one=;
null->ch[]=null->ch[]=null;
for(int i=;i<(MAXN<<);i++) root[i]=null;
for(int i=;i<(MAXN<<);i++) stack[++top]=pool+i;
}
inline ScapeGoat_Tree *New(int key,int i)
{
ScapeGoat_Tree *p;
p=stack[top--];
p->size=p->cover=p->ex=;
p->max_army=p->max_one=;
p->key=key;
p->num=i;
p->ch[]=p->ch[]=null;
return p;
}
void travel(ScapeGoat_Tree *p)
{
if(p==null)return;
pushdown(p);
travel(p->ch[]);
if(p->ex)lst[++len]=p;
else stack[++top]=p;
travel(p->ch[]);
}
ScapeGoat_Tree *divide(int l,int r)
{
if(l>r)return null;
int mid=(l+r)>>;
lst[mid]->ch[]=divide(l,mid-);
lst[mid]->ch[]=divide(mid+,r);
lst[mid]->pushup();
return lst[mid];
}
inline void rebuild(ScapeGoat_Tree *&p)
{
len=;
travel(p);
p=divide(,len);
}
ScapeGoat_Tree **insert(ScapeGoat_Tree *&p,int key,int i)
{
if(p==null)
{
p=New(key,i);
return &null;
}
pushdown(p);
p->size++;
p->cover++;
ScapeGoat_Tree **ret=insert(p->ch[p->key<=key],key,i);
if(p->bad())ret=&p;
return ret;
}
inline int Rank(ScapeGoat_Tree *Root,int k)
{
ScapeGoat_Tree *now=Root;
while(now!=null)
if(now->ex&&now->ch[]->size+==k) return now->key;
else if(now->ch[]->size>=k) now=now->ch[];
else k-=now->ch[]->size+now->ex,now=now->ch[];
return ;
}
inline int Kth(ScapeGoat_Tree *Root,int key)
{
ScapeGoat_Tree *now=Root;
int ret=;
while(now!=null)
if(now->key>=key)
now=now->ch[];
else
ret+=now->ch[]->size+now->ex,now=now->ch[];
return ret;
}
inline void Insert(ScapeGoat_Tree *&Root,int key,int i)
{
Max_army[i]=Max(Max_army[i],Rank(Root,));
if(Root!=null)
Root->max_army=Max(Root->max_army,key);
ScapeGoat_Tree **p=insert(Root,key,i);
if(*p!=null)rebuild(*p);
Root->max_one=Max(Root->max_one,Root->size);
}
void Delete_Kth(ScapeGoat_Tree *p,int k)
{
pushdown(p);
p->size--;
if(p->ex&&p->ch[]->size+==k)
{
p->ex=;
return;
}
if(p->ch[]->size>=k) Delete_Kth(p->ch[],k);
else Delete_Kth(p->ch[],k-p->ch[]->size-p->ex);
}
inline void Delete(ScapeGoat_Tree *&Root,int key)
{
Delete_Kth(Root,Kth(Root,key));
if(Root->size<Root->cover*a)rebuild(Root);
}
void dfs(ScapeGoat_Tree *p)
{
if(p==null)return;
pushdown(p);
dfs(p->ch[]);
dfs(p->ch[]);
}
int main()
{
//freopen("bird.in","r",stdin);
//freopen("bird.out","w",stdout);
Init();
scanf("%d",&n);
for(int i=;i<=n;i++)
{
int x,y;
scanf("%d%d%d",&w[i],&x,&y);
int p=bird[hash(x,y)];
if(!p) p=bird[hash(x,y)]=++sz;
pos[i]=p;
Insert(root[p],w[i],i);
}
scanf("%d",&t);
for(int i=;i<=t;i++)
{
int v,x,y;
scanf("%d%d%d",&v,&x,&y);
int p=bird[hash(x,y)];
if(!p) p=bird[hash(x,y)]=++sz;
Delete(root[pos[v]],w[v]);
pos[v]=p;
Insert(root[p],w[v],v);
}
for(int i=;i<=sz;i++)
dfs(root[i]);
for(int i=;i<=n;i++)
{
LL ans=(LL)(Max_one[i]-)*Max_army[i];
printf("%lld\n",ans);
}
return ;
}
最新文章
- 0040 Java学习笔记-多线程-线程run()方法中的异常
- ASP.NET MVC 路由(四)
- UVALive 7267	Mysterious Antiques in Sackler Museum (判断长方形)
- 开源 P2P 直播 视频会议
- Linux守护进程daemon
- (二)Eclipse 快捷键
- CentOS6.7 常用操作命令
- struts2 的struts.xml配置详解
- Linux脚本学习随记
- 【JAVAWEB学习笔记】网上商城实战:环境搭建和完成用户模块
- C语言 时间函数的学习
- Mark一下~
- autotrace执行计划中,统计信息详解
- 【leetcode】453. Minimum Moves to Equal Array Elements
- pandas dataframe 过滤——apply最灵活!!!
- 03.获取页面的flash文件
- lumen框架的辅助函数
- css布局笔记(二)Flex
- Nginx学习笔记(三)------配置文件nginx.conf说明
- ssh-copy-id使用非默认22端口