24pts 求调
查看原帖
24pts 求调
602370
SLPing楼主2025/2/2 11:37

测试点5中维护的前缀最大值序列长度(len)(len)会多1 和(sum)(sum) 也对不上。（数据在底下）

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int _=1e6+5;
int n,_n,m,k;
int z[_],dep[_],l[_],r[_],to[_],sum[_];
vector<int>s[_];
set<int>ask;
void dfs(int x){
	l[x]=++k,to[k]=x;
	for(auto i:s[x])
		dep[i]=dep[x]+z[x],dfs(i);
	r[x]=k;
}
struct xds{
	struct da{
		int x,y,lx,rx,lmax,rmax,len,sum,pd;
		void put(){
			printf("%lld %lld %lld %lld %lld %lld %lld %lld\n",x,y,lx,rx,lmax,rmax,len,sum);
		}
	}ans,s[4*_];
	struct sp{
		int len,sum;
		const sp operator + (const sp& x) const{
			return {len+x.len,sum+x.sum};
		}
	};
	void add(int k,int p){
		s[k].x+=p,s[k].y+=p,s[k].pd+=p;
		if(s[k].lx)
			s[k].lmax+=p,s[k].rmax+=p,s[k].sum+=s[k].len*p;
	}
	void push_down(int k){
		if(s[k].pd)
			add(2*k,s[k].pd),add(2*k+1,s[k].pd);
		s[k].pd=0;
	}
	sp get(int k,int minn,int p){
		push_down(k);
		if(s[k].x<minn||s[k].lx==s[k].rx)
			return sp{0ll,0ll};
		if(s[k].x>=p)
			return sp{s[k].len,s[k].sum};
		if(s[2*k].x==s[2*k+1].x){
			if(s[2*k].y>=p)
				return get(2*k,minn,p)+sp{s[k].len-s[2*k].len,s[k].sum-s[2*k].sum};
			if(s[2*k].rx&&s[2*k+1].lx&&max(s[2*k].rmax,s[2*k+1].lmax)>=p)
				return sp{s[k].len-s[2*k].len,s[k].sum-s[2*k].sum};
			return get(2*k+1,minn,p);
		}
		if(s[2*k].x<s[2*k+1].x)
			return get(2*k,minn,p);
		return get(2*k+1,minn,p);
	}
	da add(da x,da y,int id){
		if(x.x<y.x)
			return x.y=max(x.y,y.y),x.rmax=max(x.rmax,y.y),x.pd=0,x;
		if(x.x>y.x)
			return y.y=max(y.y,x.y),y.lmax=max(y.lmax,x.y),y.pd=0,y;
		da st=x;
		int p=max(x.rmax,y.lmax);
		if(p>=x.y&&x.rx&&y.lx)
			st.len++,st.sum+=p;
		sp lst=get(id,x.x,x.rx&&y.lx?max(p,x.y):x.y);
		st.x=min(x.x,y.x),st.y=max(x.y,y.y);
		st.lx=st.lx?st.lx:y.lx,st.rx=y.rx?y.rx:st.rx;
		st.lmax=x.lx?x.lmax:max(y.lmax,x.y),st.rmax=y.rmax?y.rmax:max(x.rmax,y.y);
		st.len+=lst.len,st.sum+=lst.sum,st.pd=0;
		return st;
	}
	void build(int l,int r,int k){
		if(l==r){
			s[k].x=s[k].y=dep[to[l]];
			if(z[to[l]]){
				s[k].lx=s[k].rx=l;
				s[k].lmax=s[k].rmax=dep[to[l]];
				s[k].len=0,s[k].sum=0;
			}
			return ;
		}
		int mid=(l+r)>>1;
		build(l,mid,2*k);
		build(mid+1,r,2*k+1);
		s[k]=add(s[2*k],s[2*k+1],2*k+1);
	}
	void change(int l,int r,int k,int x,int y,int p){
		if(x<=l&&r<=y){
			add(k,p);
			return ;
		}
		push_down(k);
		int mid=(l+r)>>1;
		if(x<=mid)
			change(l,mid,2*k,x,y,p);
		if(mid<y)
			change(mid+1,r,2*k+1,x,y,p);
		s[k]=add(s[2*k],s[2*k+1],2*k+1);
	}
	void _change(int l,int r,int k,int x){
		if(l==r){
			if(z[to[l]]){
				s[k].lx=s[k].rx=0;
				s[k].lmax=s[k].rmax=0;
				s[k].len=0,s[k].sum=0;
			}
			else{
				s[k].lx=s[k].rx=l;
				s[k].lmax=s[k].rmax=dep[to[l]];
				s[k].len=0,s[k].sum=0;
			}
			return ;
		}
		push_down(k);
		int mid=(l+r)>>1;
		if(x<=mid)
			_change(l,mid,2*k,x);
		else
			_change(mid+1,r,2*k+1,x);
		s[k]=add(s[2*k],s[2*k+1],2*k+1);
	}
	void find(int l,int r,int k,int x,int y){
		if(x<=l&&r<=y){
			ans=add(ans,s[k],k);
			return;
		}
		push_down(k);
		int mid=(l+r)>>1;
		if(x<=mid)
			find(l,mid,2*k,x,y);
		if(mid<y)
			find(mid+1,r,2*k+1,x,y);
		s[k]=add(s[2*k],s[2*k+1],2*k+1);
	}
	da _find(int x,int y){
		ans={(int)1e9,0,0,0,0,0,0,0,0};
		find(1,n,1,x,y);
		return ans;
	}
}_s;
signed main(){
	freopen("1.in","r",stdin);
	scanf("%lld%lld",&n,&m),_n=n;
	for(int i=1,x;i<=_n;i++){
		scanf("%lld%lld",&z[i],&x);
		for(int j=1,t;j<=x;j++){
			scanf("%lld",&t);
			s[i].push_back(t);
		}
		if(!x)
			s[i].push_back(++n);
	}
	dfs(1),_s.build(1,n,1);
	for(int i=1;i<=n;i++){
		if(z[i])
			ask.insert(l[i]);
	}
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+(i==r[to[i]]?1:0);
	ask.insert(n+1);
	while(m--){
		int pd,x;
		scanf("%lld%lld",&pd,&x);
		if(pd==1){
			!z[x]?ask.insert(l[x]),void():(ask.erase(l[x]),void());
			_s.change(1,n,1,l[x]+1,r[x],z[x]?-1:1);
			_s._change(1,n,1,l[x]),z[x]=1-z[x];
		}
		else{
			int st=*ask.lower_bound(l[x]);
			if(st>r[x]){
				printf("%lld\n",sum[r[x]]-sum[l[x]-1]+(sum[r[x]]-sum[l[x]-1]>=2?1:0));
				continue;
			}
			_s._find(l[x],r[x]);
			if(_s.ans.rmax>=_s.ans.y)
				_s.ans.len++,_s.ans.sum+=_s.ans.rmax;
			printf("%lld\n",sum[st-1]-sum[l[x]-1]+_s.ans.sum-_s.ans.len*_s.ans.x+(sum[st-1]-sum[l[x]-1]+_s.ans.len>=2?1:0));
//			for(int i=1;i<=n;i++)
//				_s._find(l[i],r[i]),_s.ans.put();
		}
	}
}

输入：

72 400
0 20 57 56 45 69 44 70 66 63 71 67 20 64 42 46 54 58 36 48 22 2
1 2 3 4
1 0
0 2 19 5
0 2 18 6
0 2 17 7
1 2 16 8
1 2 14 9
0 2 12 10
1 1 11
1 0
1 1 13
1 0
1 1 15
1 0
1 0
1 0
1 0
1 0
1 1 21
1 0
0 2 23 24
1 0
1 2 35 25
0 2 26 27
1 0
0 2 34 28
1 2 29 31
1 1 30
1 0
1 2 32 33
1 0
1 0
1 0
1 0
1 2 37 38
1 0
0 2 41 39
1 1 40
1 0
1 0
1 1 43
1 0
1 0
1 0
1 1 47
1 0
1 2 49 50
1 0
1 2 53 51
1 1 52
1 0
1 0
1 1 55
1 0
1 0
1 0
0 2 59 60
1 0
0 2 62 61
1 0
1 0
1 0
1 1 65
1 0
1 0
1 1 68
1 0
1 0
1 0
1 1 72
1 0
1 29
1 38
1 39
1 66
1 52
1 30
1 42
1 26
1 62
1 33
1 6
1 14
1 25
1 19
1 17
1 43
1 10
1 13
1 8
1 60
1 39
1 28
1 8
1 31
1 24
1 50
1 18
1 32
1 29
1 17
1 39
1 33
1 10
1 13
1 42
1 25
1 34
1 41
1 32
2 1
1 53
1 39
1 10
1 9
1 15
1 22
1 5
1 11
1 34
1 16
1 7
1 49
1 10
1 15
1 65
1 10
1 39
1 11
1 52
1 55
1 7
1 16
1 3
1 10
1 4
1 21
1 31
1 34
1 13
1 30
1 52
1 28
1 54
1 32
1 11
1 13
1 70
1 32
1 27
2 1
1 30
1 23
1 26
1 16
1 14
1 66
1 25
1 17
1 11
1 8
1 34
1 31
1 11
1 14
1 12
1 8
1 59
1 61
1 10
1 30
1 13
1 36
1 14
1 11
1 15
1 51
1 29
1 13
1 13
1 11
1 5
1 11
1 25
1 11
1 28
1 10
1 40
1 15
1 32
2 1
1 10
1 64
1 52
1 5
1 64
1 37
1 15
1 16
1 17
1 13
1 15
1 9
1 7
1 30
1 32
1 41
1 42
1 32
1 9
1 29
1 52
1 32
1 30
1 10
1 11
1 34
1 37
1 13
1 28
1 7
1 18
1 14
1 51
1 41
1 65
1 10
1 9
1 15
1 52
2 1
1 39
1 31
1 11
1 72
1 30
1 19
1 14
1 33
1 26
1 15
1 32
1 51
1 26
1 31
1 13
1 33
1 48
1 17
1 12
1 29
1 18
1 18
1 29
1 19
1 33
1 32
1 4
1 32
1 32
1 70
1 64
1 11
1 43
1 18
1 9
1 15
1 27
1 57
1 31
2 1
1 10
1 19
1 13
1 12
1 12
1 17
1 14
1 40
1 31
1 10
1 34
1 33
1 47
1 12
1 29
1 17
1 8
1 62
1 16
1 30
1 31
1 14
1 10
1 31
1 17
1 7
1 33
1 17
1 8
1 18
1 32
1 11
1 14
1 62
1 61
1 40
1 43
1 11
1 14
2 1
1 57
1 11
1 56
1 7
1 3
1 10
1 52
1 52
1 52
1 28
1 10
1 32
1 14
1 15
1 19
1 27
1 34
1 26
1 54
1 10
1 33
1 26
1 32
1 21
1 21
1 62
1 16
1 12
1 15
1 11
1 29
1 17
1 6
1 32
1 26
1 12
1 31
1 9
1 30
2 1
1 9
1 12
1 30
1 35
1 7
1 55
1 27
1 12
1 11
1 12
1 26
1 52
1 34
1 16
1 13
1 14
1 39
1 11
1 9
1 35
1 15
1 15
1 15
1 51
1 33
1 14
1 15
1 8
1 11
1 29
1 31
1 8
1 61
1 68
1 15
1 12
1 11
1 29
1 16
2 1
1 10
1 6
1 19
1 29
1 35
1 10
1 7
1 19
1 29
1 13
1 10
1 33
1 15
1 28
1 22
1 20
1 37
1 45
1 13
1 14
1 7
1 42
1 8
1 15
1 30
1 25
1 7
1 5
1 35
1 17
1 13
1 10
1 18
1 13
1 33
1 30
1 39
1 17
1 53
2 1
1 57
1 14
1 70
1 15
1 59
1 9
1 53
1 8
1 11
1 17
1 6
1 14
1 52
1 40
1 9
1 53
1 26
1 13
1 13
1 28
1 14
1 10
1 19
1 58
1 61
1 13
1 32
1 32
1 27
1 30
1 12
1 8
1 50
1 11
1 9
1 13
1 13
1 57
1 16
2 1

输出：

31
32
24
31
28
26
24
26
29
27
2025/2/2 11:37