t1 Baekjoon 21527
给定 \(n\times n\) 矩阵 \(a\)，对于 \((i,j)\) 求 \((1,1)\) 到 \((n,n)\) 最短路径上与 \(a_{i,j}\) 相同数的个数的最大值。
唐氏症题。
每种 \(a\) 单独提出来，\(f_{i,j}\) 为 \((i,j)\) 的答案，转移形如 \(\max_{x\le i,y\le j}f_{i,j}=f_{x,y}+1\)。形如二维偏序，随便整个数据结构维护。
#include<bits/stdc++.h>
#define fin(x) freopen(#x".in","r",stdin)
#define fout(x) freopen(#x".out","w",stdout)
#define fr(x) fin(x),fout(x);
#define Fr(x,y) fin(x),fout(y)
#define INPUT(_1,_2,FILE,...) FILE
#define IO(...) INPUT(__VA_ARGS__,Fr,fr)(__VA_ARGS__)
using namespace std;
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define ll long long
#define ull unsigned long long
#define intz(x,y) memset((x),(y),sizeof((x)))
inline int lowbit(int x){return x&-x;}
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline ll read(){ll x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}while(ch>=48&&ch<=57)x=x*10+ch-48,ch=nc();return x*f;
}
const int N=1505;
int a[N][N],t[N],f[N][N],g[N][N],ans[N],n;vector<pii>q[N*N];
void clr(int x){for(int X=x;X<=n;X+=lowbit(X))t[X]=0;for(int X=x;X;X-=lowbit(X))t[X]=0;
}
void upd(int x,int d){for(;x<=n;x+=lowbit(x))t[x]=max(t[x],d);}
int ask(int x){int res=0;for(;x;x-=lowbit(x))res=max(res,t[x]);return res;}
void upd_(int x,int d){for(;x;x-=lowbit(x))t[x]=max(t[x],d);}
int ask_(int x){int res=0;for(;x<=n;x+=lowbit(x))res=max(res,t[x]);return res;}
inline void UesugiErii(){cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j],q[a[i][j]].pb(mp(i,j));for(int i=1;i<=n*n;i++){vector<int>p;sort(q[i].begin(),q[i].end());int lst=0;for(int j=0;j<q[i].size();j++){pii x=q[i][j];f[x.fi][x.se]=ask(x.se)+1;upd(x.se,f[x.fi][x.se]),p.pb(x.se);}for(int j:p)clr(j);p.clear();lst=q[i].size()-1;for(int j=q[i].size()-1;~j;j--){pii x=q[i][j];g[x.fi][x.se]=ask_(x.se)+1,++ans[f[x.fi][x.se]+g[x.fi][x.se]-1];upd_(x.se,g[x.fi][x.se]),p.pb(x.se);}for(int j:p)clr(j);p.clear();}for(int i=1;i<(n<<1);i++)cout<<ans[i]<<'\n';
}
signed main(){cfast;int _=1;//cin>>_;for(;_;_--)UesugiErii();return 0;
}
t2
\(m\) 个数，\(n\) 次操作，每次操作求 \([l,r]\) 内最大最小原始编号。将 \([l,r]\) 内下标与 \(l\) 奇偶性相同的元素删去，剩下元素补到前面。
唐氏症题。想了半天直接维护。
线段树维护区间剩余元素个数，以及操作标记 0/1 表示从开头/开头+1 位置开始删的操作。发现标记无法合并，但是注意到每次操作元素个数减小一倍，一个区间有效操作次数 \(log\) 量级的，故维护操作队列。
#include<bits/stdc++.h>
#define fin(x) freopen(#x".in","r",stdin)
#define fout(x) freopen(#x".out","w",stdout)
#define fr(x) fin(x),fout(x);
#define Fr(x,y) fin(x),fout(y)
#define INPUT(_1,_2,FILE,...) FILE
#define IO(...) INPUT(__VA_ARGS__,Fr,fr)(__VA_ARGS__)
using namespace std;
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define ll long long
#define ull unsigned long long
#define intz(x,y) memset((x),(y),sizeof((x)))
inline int lowbit(int x){return x&-x;}
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline ll read(){ll x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}while(ch>=48&&ch<=57)x=x*10+ch-48,ch=nc();return x*f;
}
#define int ll
const int N=1e5+5;
struct sgt{int rt,tot;struct node{int ls,rs;ll x;vector<bool>laz;}t[N*60];void pushup(int u){t[u].x=t[t[u].ls].x+t[t[u].rs].x;}void add(int u,bool f){if(t[u].x)t[u].laz.pb(f);t[u].x=(f?t[u].x+1:t[u].x)/2;}void pd(int u,ll l,ll r){ll mid=l+r>>1;if(!t[u].ls)t[t[u].ls=++tot].x=mid-l+1;if(!t[u].rs)t[t[u].rs=++tot].x=r-mid;for(int i=0,laz;i<t[u].laz.size();i++){laz=(t[t[u].ls].x&1)?!t[u].laz[i]:t[u].laz[i];add(t[u].ls,t[u].laz[i]),add(t[u].rs,laz);}t[u].laz.clear();}ll upd(int &u,ll l,ll r,ll lf,ll rt,ll X){if(!u)t[u=++tot].x=r-l+1;if(l>=lf&&r<=rt){ll q=t[u].x;return add(u,X&1),q;}ll mid=l+r>>1,res=0;pd(u,l,r);if(lf<=mid)res+=upd(t[u].ls,l,mid,lf,rt,X);if(rt>mid)res+=upd(t[u].rs,mid+1,r,lf,rt,X+res);pushup(u);return res;}ll get(int u,ll l,ll r,ll x){if(l==r)return l;ll mid=l+r>>1;pd(u,l,r);if(t[t[u].ls].x>=x)return get(t[u].ls,l,mid,x);else return get(t[u].rs,mid+1,r,x-t[t[u].ls].x);}
}t;
inline void UesugiErii(){ll n,m;cin>>n>>m;while(n--){ll l,r,L,R;cin>>l>>r;L=t.get(t.rt,1,m,l),R=t.get(t.rt,1,m,r);cout<<L<<' '<<R<<'\n';t.upd(t.rt,1,m,L,R,0);}
}
signed main(){cfast;int _=1;//cin>>_;for(;_;_--)UesugiErii();return 0;
}