挂分场
复盘
决定尝试一下多放一点时间在前期看题上
T1 发现是模拟；T2 看上去好神秘啊！想了一会一直没什么思路；T3 看上去眼熟，但还是觉得计数很困难；T4 看完发现是数据结构，推了推很快会了树高做法，感觉这个很好拓展啊！就多推了一会，最后思路大概是操作分块，但块内贡献不会处理
一直到 8:30 才开始码，8:40 交了 T1
推 T2，仔细开始分析，首先
l
1
,
l
2
l_1,l_2
l1,l2 肯定是
1
1
1，然后按位考虑，发现
l
1
l_1
l1 肯定要取在第一个
1
1
1 的位置，又讨论了一下发现直接贪心做完了？这么诈骗
9:20 交了，看大样例强度感觉还可以，应该不是很能挂（
T3 换题了，才知道是之前 daimayuan 的原题 但是我不记得 ，换之后感觉比之前好做了，更符合我那个贪心判定的思路
还是找性质，首先肯定从小到大贪心匹配，然后发现单点操作一定优于顺子操作，然后状态很少，然后就会暴力 dp 了，然后正解感觉上矩乘就行了？
先写了暴力 dp，发现过了样例；改矩乘，调了一会也过了样例，10:30 交了
还有 1.5h 多，感觉很稳
先看了看部分分，发现 45pts 是简单的，后面的链感觉应该是在提示正解
还是在想最开始那个基于树高的做法，从每个点往上暴力跳，贡献是可以直接算的。那么本质上是链求和，然后对若干完全不连续的点进行点权修改
链的话显然可以分块，考虑某个前缀对整块的贡献
但是有问题，这是区间赋值，不像加加减减可以直接拼贡献，想了很久灵光一现：ODT！
对啊，基于颜色段均摊，赋值操作就可以拆成若干个区间加和区间撤销，这就可以维护了
每次怎么查答案呢？貌似只能暴力枚举每一段了，整段对单点就只需要查祖先链中某一段区间内的贡献就行，主席树即可
但这需要满足询问区间随机，段数是 log \log log 才可以
此时就剩 50min 了，反复权衡了一下感觉 ODT 会比较难写，还可能会被卡，决定写暴力吧
于是在大概 40min 的时间里写了 6 个 k，每个 sub 只过了手造的数据
然后就结束了
结果是：
100 + 0 + 100 + 35 = 235 100 + 0 + 100 + 35 = 235 100+0+100+35=235
蚌，T2 挂没了，发现是没有判 S S S 里全是 0 0 0 的情况，我直接没输出。。。而且它数据是每个 sub 里捆一个这种点，逆天
T4 挂了 10pts，原因是 p a i r pair pair 的 f i r s t first first 和 s e c o n d second second 弄反了
感觉有点亏啊！下午去实现 T4 ODT 的思路，发现不但十分好写，而且能有 90pts，拼上下午写的一个 sub 就过了
感觉有时候还是要自信点的
听正解，发现赛时是因为没有深入分析贡献的方式，只是觉得能做但是挺复杂的，仔细分讨完之后其实情况十分简单，直接基于这个算贡献就行
题解
还是先说贡献方式，发现对于节点
x
x
x，需要实时维护的只有两种：
1. 1. 1. x ∈ l s o n ( y ) , v y = − 1 x\in lson(y),v_y=-1 x∈lson(y),vy=−1，那么 x x x 会加 1 1 1
2. 2. 2. x ∈ r s o n ( y ) , v y = 1 x\in rson(y),v_y=1 x∈rson(y),vy=1，那么 x x x 会减 1 1 1
考虑分块，整块的权值都一样时情况是比较好处理的，那么直接预处理出贡献系数数组 f x , i f_{x,i} fx,i 表示 第 i i i 个整块中有多少个 y y y 分别满足上面的条件，算答案时直接枚举每个整块
对于散块，先考虑单点，把这个放在修改时处理，枚举每个散块中的每个单点，直接进行子树加减
然而有个问题是把散块变成整块时需要撤销贡献，发现这个直接暴力做就行
具体来说，把块分为两类：有整块标记的，块内不一定统一的
进行整块枚举时，如果发现这是二类块，直接暴力枚举所有位置撤销贡献即可，由于颜色段均摊，这样复杂度显然也是对的
#include<bits/stdc++.h>//嘿嘿，ODT 才是最强的
using namespace std ;
typedef long long LL ;
const int N = 1e5+10 ;
int n , Q , ls[N] , rs[N] ;
int op[N] , l[N] , r[N] , id[N] ;
struct Segtree
{
int ls , rs , cnt0 , cnt1 ;
}t[40*N] ;//作为左儿子往上跳/作为右儿子往上跳的节点编号
int rt[N] , tot ;
inline int build() { return ++tot ; }
inline void update( int p )
{
t[p].cnt0 = t[t[p].ls].cnt0 + t[t[p].rs].cnt0 ;
t[p].cnt1 = t[t[p].ls].cnt1 + t[t[p].rs].cnt1 ;
}
int Insert( int p , int l , int r , int x , bool f )
{
int nw = build() ;
t[nw] = t[p] ;
if( l == r ) {
if( !f ) t[nw].cnt0 ++ ;
else t[nw].cnt1 ++ ;
return nw ;
}
int mid = (l+r)>>1 ;
if( x <= mid ) t[nw].ls = Insert(t[p].ls,l,mid,x,f) ;
else t[nw].rs = Insert(t[p].rs,mid+1,r,x,f) ;
update(nw) ;
return nw ;
}
typedef pair<int,int> PII ;
PII query( int p , int l , int r , int ql , int qr )
{
if( !p ) return {0,0} ;
if( ql <= l && r <= qr ) {
return {t[p].cnt0,t[p].cnt1} ;
}
int mid = (l+r)>>1 ;
if( ql > mid ) return query(t[p].rs,mid+1,r,ql,qr) ;
if( qr <= mid ) return query(t[p].ls,l,mid,ql,qr) ;
PII R1 = query(t[p].ls,l,mid,ql,qr) , R2 = query(t[p].rs,mid+1,r,ql,qr) ;
return {R1.first+R2.first,R1.second+R2.second} ;
}
int siz[N] , val[N] ;
void dfs( int x )
{
siz[x] = 1 ;
if( ls[x] ) {
rt[ls[x]] = Insert( rt[x] , 1 , n , x , 0 ) ;
dfs(ls[x]) ;
}
if( rs[x] ) {
rt[rs[x]] = Insert( rt[x] , 1 , n , x , 1 ) ;
dfs(rs[x]) ;
}
siz[x] += siz[ls[x]] + siz[rs[x]] ;
}
void get_val( int x )
{
if( ls[x] ) {
val[ls[x]] = val[x] ;
get_val(ls[x]) ;
}
if( rs[x] ) {
val[rs[x]] = val[x]+siz[ls[x]]+1 ;
get_val(rs[x]) ;
}
}
struct node
{
int l , r , v ;
friend bool operator < ( node a , node b ) {
return a.l<b.l ;
}
};
struct np
{
int l , r , v ;
}tmp[N] ;
int len ;
set<node> s ;
auto Split( int x ) // 分裂 x-1,x ,返回 x 段迭代器
{
auto it = s.lower_bound({x,0,0}) ;
if( it != s.end() && it->l == x ) return it ;
it -- ;
if( it->r < x ) return s.end() ;
int l = it->l , r = it->r , v = it->v ;
s.erase(it) ;
s.insert({l,x-1,v}) ;
return s.insert({x,r,v}).first ;
}
void Assign( int l , int r , int v )
{
auto itr = Split(r+1) , itl = Split(l) ;//顺序不能换
s.erase( itl , itr ) ;
s.insert((node){l,r,v}) ;
}
int Max ;
void Ask( int x )
{
int ans = val[x] , v ;
auto it = s.lower_bound({x,0,0}) ;
if( it->l==x ) v = it->v ;
else v = (--it)->v ;
if( v==-1 ) ans += 1 ;
else if( v==0 ) ans += siz[ls[x]]+1 ;
else ans += siz[ls[x]]+siz[rs[x]]+1 ;
// printf("%d\n" , ans ) ;
len = 0 ;
for(auto it = s.begin() ; it != s.end() ; it ++ ) {
int l = it->l , r = it->r , v = it->v ;
tmp[++len] = {l,r,v} ;
PII R = query(rt[x],1,n,l,r) ;
// printf("query rt %d , l=%d , r=%d\n" , x , R.first , R.second ) ;
if( v==-1 ) ans += R.first ;
if( v==1 ) ans -= R.second ;
}
s.clear() ;
int nl = tmp[1].l , nv = tmp[1].v , nr = tmp[1].r ;
for(int i = 2 ; i <= len+1 ; i ++ ) { // 合并一下
if( tmp[i].v==nv && i != len+1 ) nr = tmp[i].r ;
else {
s.insert({nl,nr,nv}) ;
nl = tmp[i].l , nr = tmp[i].r , nv = tmp[i].v ;
}
}
printf("%d\n" , ans ) ;
}
namespace subtask4
{
int dfn[N] , tim , ed[N] , v[N] , nam[N] ;
void dfs( int x )
{
dfn[x] = ++tim ;
if( ls[x] ) dfs(ls[x]) ;
if( rs[x] ) dfs(rs[x]) ;
ed[x] = tim ;
}
struct BIT
{
int t[N] ;
inline int lowbit( int x ) { return x&-x ; }
void add( int p , int x ) {
for( ; p <= n ; p += lowbit(p) ) t[p] += x ;
}
int ask( int p ) {
int res = 0 ;
for( ; p ; p -= lowbit(p) ) res += t[p] ;
return res ;
}
void Add( int l , int r , int x )
{
add(l,x) ;
if( r < n ) add(r+1,-x) ;
}
} T ;
void Rem( int x )
{
if( v[x]==-1 ) {
if( ls[x] ) T.Add(dfn[ls[x]],ed[ls[x]],-1) ;
if( rs[x] ) T.Add(dfn[rs[x]],ed[rs[x]],-(1+siz[ls[x]])) ;
}
else if( v[x]==0 ) {
if( rs[x] ) T.Add(dfn[rs[x]],ed[rs[x]],-(1+siz[ls[x]]) ) ;
}
else {
if( rs[x] ) T.Add(dfn[rs[x]],ed[rs[x]],-siz[ls[x]]) ;
}
}
void Add( int x )
{
if( v[x]==-1 ) {
if( ls[x] ) T.Add(dfn[ls[x]],ed[ls[x]],1) ;
if( rs[x] ) T.Add(dfn[rs[x]],ed[rs[x]],1+siz[ls[x]]) ;
}
else if( v[x]==0 ) {
if( rs[x] ) T.Add(dfn[rs[x]],ed[rs[x]],1+siz[ls[x]]) ;
}
else {
if( rs[x] ) T.Add(dfn[rs[x]],ed[rs[x]],siz[ls[x]]) ;
}
}
void solve() //单点修改
{
dfs(1) ;
for(int i = 1 ; i <= n ; i ++ ) {
v[i] = -1 , Add(i) ;
}
for(int i = 1 ; i <= Q ; i ++ ) {
if( op[i] == 1 ) {
Rem(l[i]) ;
v[l[i]] = id[i] ;
Add(l[i]) ;
}
else {
int ans = 0 ;
int x = id[i] ;
if( v[x]==-1 ) ans = 1 ;
else if( v[x]==0 ) ans = siz[ls[x]]+1 ;
else ans = siz[ls[x]]+siz[rs[x]]+1 ;
printf("%d\n" , ans+T.ask(dfn[x]) ) ;
}
}
}
}
int main()
{
scanf("%d%d" , &n , &Q ) ;
for(int i = 1 ; i <= n ; i ++ ) {
scanf("%d%d" , &ls[i] , &rs[i] ) ;
}
rt[1] = build() ;
dfs(1) ;
get_val(1) ;
// cout << val[1] << ' ' << val[2] << endl ;
s.insert({1,n,-1}) ;
bool fg2 = 0 ;
for(int i = 1 ; i <= Q ; i ++ ) {
scanf("%d" , &op[i] ) ;
if( op[i] == 1 ) {
scanf("%d%d%d" , &l[i] , &r[i] , &id[i] ) ;
if( l[i]!=r[i] ) fg2 = 1 ;
}
else {
scanf("%d" , &id[i] ) ;
}
}
if( !fg2 ) {
subtask4::solve() ;
return 0 ;
}
for(int i = 1 ; i <= Q ; i ++ ) {
if( op[i] == 1 ) {
Assign(l[i],r[i],id[i]) ;
}
else {
Ask(id[i]) ;
}
}
return 0 ;
}
