Lomsat gelral
把树拍成一条链，询问子树等于询问区间。
这样一看这道题就非常莫队。
但是有要求个数最多的颜色的编号，我们可以用线段树动态维护颜色的最大值。
这样，一个无脑莫队线段树的暴力就做出来了。
int n,a[N];
int dfn[N],nfd[N],cnt;
int b[N],siz[N];
vector<int>g[N];
inline void dfs(int u,int from){
dfn[u]=++cnt;nfd[cnt]=u;
b[cnt]=a[u];
siz[u]=1;
for(auto v:g[u]){
if(v==from)continue;
dfs(v,u);
siz[u]+=siz[v];
}
}
struct ask{
int l,r,id;
}q[N];
int pos[N],blo;
inline bool cmp(ask x,ask y){
if(pos[x.l]!=pos[y.l])return pos[x.l]<pos[y.l];
if(pos[x.l]&1)return x.r>y.r;
return x.r<y.r;
}
int ans[N];
int coln[N];
struct SegmentTree{
struct node{
int l,r,maxl,maxpos;
}tr[N<<2];
inline void push_up(int k){
tr[k].maxl=max(tr[lc].maxl,tr[rc].maxl);
if(tr[k].maxl==tr[lc].maxl)tr[k].maxpos+=tr[lc].maxpos;
if(tr[k].maxl==tr[rc].maxl)tr[k].maxpos+=tr[rc].maxpos;
}
inline void build(int k,int l,int r){
tr[k].l=l;tr[k].r=r;
if(l==r){
tr[k].maxl=0;
tr[k].maxpos=l;
return;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
push_up(k);
}
inline void add(int k,int l,int r,int val){
if(tr[k].l>=l&&tr[k].r<=r){
tr[k].maxl+=val;
return;
}
int mid=(tr[k].l+tr[k].r)>>1;
if(mid>=l)add(lc,l,r,val);
if(mid<r)add(rc,l,r,val);
push_up(k);
}
}T;
inline void add(int x){
T.add(1,x,x,1);
}
inline void del(int x){
T.add(1,x,x,-1);
}
signed main(){
n=read();
blo=sqrt(n);
up(i,1,n){
a[i]=read();
pos[i]=(i-1)/blo+1;
}
int u,v;
up(i,1,n-1){
u=read();v=read();
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
up(i,1,n){
q[i].l=dfn[i];
q[i].r=dfn[i]+siz[i]-1;
q[i].id=i;
}
T.build(1,1,n);
sort(q+1,q+1+n,cmp);
int L=1,R=0;
up(i,1,n){
while(R<q[i].r)add(b[++R]);
while(R>q[i].r)del(b[R--]);
while(L>q[i].l)add(b[--L]);
while(L<q[i].l)del(b[L++]);
ans[q[i].id]=T.tr[1].maxpos;
}
up(i,1,n)write(ans[i],0);
return 0;
}
当然，这道题正解应该是 \(dsu\ on\ tree\)。
用树上启发式合并又该怎么做呢？
我们先考虑暴力，对每一个点搜索其子树，暴力查询自树中颜色最多的颜色。
这个的复杂度是 \(O(n^2)\) 的。
但是我们发现，对于每个节点 \(v\)，最后一棵子树是不用清空的，因为做完那棵子树后可以把其结果直接加入 \(v\) 的答案中。
那么我们选择那颗子树为 \(v\) 的重儿子。
看起来没有什么优化，实际上复杂度为 \(O(n\log n)\)。
代码我就不放了。
Frogs and mosquitoes
恶心题。
很暴力的，你可以对每一个蚊子，向前枚举最远的青蛙，这个青蛙吃到了这只蚊子，舌头变长，判断能否吃到蚊子，如果不能，加入新的蚊子。
当然，这个暴力是 \(n^2\) 的，肯定过不了。
考虑优化。
在向前枚举青蛙这一步时，我们可不可以二分，似乎是不行的。因为有青蛙的是不满足单调性的，所以我们可以预处理一下青蛙，把所有区间会被前面的青蛙完全覆盖的青蛙去掉，这样，青蛙就可以满足单调性。
所以可以二分找到最左边的青蛙。
找到那只青蛙，把舌头伸长。这时就可以对蚊子在的一个集合进行二分。找出能够吃那些蚊子。
最后记得继续删除青蛙来满足数组的单调性。
复杂度 \(O(n\log n)\)。
int n,m;
struct frog{
int x,t,id;
}a[N];
int ansl[N],ansc[N];
inline bool cmp(frog x,frog y){
if(x.x==y.x)return x.t<y.t;
return x.x<y.x;
}
int maxl=0;
vector<frog>t;
int k=0;
inline int ask(int p){
int l=1,r=k,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(t[mid].x+t[mid].t>=p){
r=mid-1;
ans=mid;
}
else l=mid+1;
}
if(t[ans].x<=p&&t[ans].x+t[ans].t>=p) return ans;
return 0;
}
multiset<pii>s;
inline void work(int x){
while(x<k){
if(t[x+1].x+t[x+1].t<=t[x].x+t[x].t) t.erase(t.begin()+x+1),k--;
else break;
}
}
signed main(){
n=read();m=read();
up(i,1,n){
a[i].x=read();
a[i].t=read();
a[i].id=i;
ansl[i]=a[i].t;
}
sort(a+1,a+1+n,cmp);
t.push_back({0,0,0});
up(i,1,n){
if(a[i].x+a[i].t>maxl){
t.push_back(a[i]);
k++;
maxl=a[i].x+a[i].t;
}
}
int x,delt;
up(i,1,m){
x=read();delt=read();
int p=ask(x);
if(p==0){
s.insert({x,delt});
continue;
}
ansl[t[p].id]+=delt;
ansc[t[p].id]++;
t[p].t+=delt;
while(!s.empty()){
auto it=s.lower_bound({t[p].x,0});
if((it==s.end())||(t[p].x+t[p].t<(it->fi))) break;
ansl[t[p].id]+=(it->se);
t[p].t+=(it->se);
ansc[t[p].id]++;
s.erase(it);
}
work(p);
}
up(i,1,n){
cout<<ansc[i]<<" "<<ansl[i]<<endl;
}
return 0;
}
New Year Tree
二进制线段树。
Zbazi in Zeydabad
又是什么奇怪的题目。
MEX Queries
我们需要维护三种操作。
- 把
[l,r]赋值为 \(1\)。- 把
[l,r]赋值为 \(0\)。- 把
[l,r]所有的数取反。
询问出现的第一个 \(0\) 的位置。
看起来就非常的珂朵莉。
struct node{
int l,r;
mutable int v;
inline bool operator<(const node&rhs)const{
return l<rhs.l;
}
};
set<node>odt;
inline auto split(int pos){
auto it=odt.lower_bound({pos,0,0});
if(it!=odt.end()&&it->l==pos)return it;
it--;
int l=it->l,r=it->r,v=it->v;
odt.erase(it);
odt.insert({l,pos-1,v});
return odt.insert({pos,r,v}).fi;
}
inline void assign(int l,int r,int v){
auto ed=split(r+1),bg=split(l);
odt.erase(bg,ed);
odt.insert({l,r,v});
}
inline void rev(int l,int r){
auto ed=split(r+1);
for(auto it=split(l);it!=ed;it++)it->v^=1;
}
inline void ask(){
for(auto it=odt.begin();it!=odt.end();it++){
if(it->v==0){
write(it->l,1);
break;
}
}
}
int n;
signed main(){
odt.insert({1,uinf,0});
n=read();
int op,l,r;
up(i,1,n){
op=read();
if(op==1){
l=read();r=read();
assign(l,r,1);
}
else if(op==2){
l=read();r=read();
assign(l,r,0);
}
else{
l=read();r=read();
rev(l,r);
}
ask();
}
return 0;
}
当然，如果不用珂朵莉树，这道题也可以做，前面三种操作可以看一下这道题：P2572 [SCOI2010] 序列操作。
把他动态开点一下就是了。
Turn Off The TV
线段树区间加，区间最小值，需要动态开点。
struct node{
int ls,rs,minl,tag;
}tr[N<<5];
int n,m,cnt=1;//一定要赋值成1
inline void push_up(int k){
tr[k].minl=min(tr[tr[k].ls].minl,tr[tr[k].rs].minl);
}
inline void push_down(int k,int l,int r){
if(tr[k].tag){
if(!tr[k].ls)tr[k].ls=++cnt;
if(!tr[k].rs)tr[k].rs=++cnt;
tr[tr[k].ls].tag+=tr[k].tag;
tr[tr[k].rs].tag+=tr[k].tag;
int mid=(l+r)>>1;
tr[tr[k].ls].minl+=tr[k].tag;
tr[tr[k].rs].minl+=tr[k].tag;
tr[k].tag=0;
}
}
inline void change(int &k,int l,int r,int x,int y,int val){
if(!k)k=++cnt;
if(x<=l&&r<=y) {
tr[k].tag+=val;
tr[k].minl+=val;
return;
}
int mid=(l+r)>>1;
push_down(k,l,r);
if(x<=mid)change(tr[k].ls,l,mid,x,y,val);
if(y>mid)change(tr[k].rs,mid+1,r,x,y,val);
push_up(k);
}
inline int ask(int k,int l,int r,int x,int y){
if(!k)return 0;
if(x<=l&&y>=r)return tr[k].minl;
push_down(k,l,r);
int mid=(l+r)>>1,res=inf;
if(x<=mid)res=min(res,ask(tr[k].ls,l,mid,x,y));
if(y>mid)res=min(res,ask(tr[k].rs,mid+1,r,x,y));
return res;
}
int L[N],R[N];
signed main(){
n=read();
int l,r;
up(i,1,n){
L[i]=read();R[i]=read();
int tmp=1;
change(tmp,0,mod,L[i],R[i],1);
}
up(i,1,n){
int tmp=1;
int t=ask(tmp,0,mod,L[i],R[i]);
if(t>=2){
cout<<i;
return 0;
}
}
cout<<-1;
return 0;
}