总览
| 题单 | 进度 | 备注 |
|---|---|---|
| 数据结构1 | 3/24 | - |
数据结构 1
STEP
读假题了，读成下面这样了：
给定 01 序列，每次单点修改，查询最长的字符相同的连续段长度
这不是一眼线段树经典板子题，分别维护左右区间信息以及合并处的信息，然后尝试在中间合并来更新答案
十五分钟光速打完拉下样例来发现不对，然后才发现自己读假题了
随后发现这俩题难道不是一个做法吗，只不过你要找的是 01010 这样的而不是 11111 这样的，所以你只有在不同的时候才能合并左右区间
所以改了个符号就过了
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,q;
namespace stree{
struct tree{
int l,r;
int maxsize;
int slize,srize;
bool lch,rch;
}t[800001];
#define tol (id*2)
#define tor (id*2+1)
#define mid(l,r) mid=((l)+(r))/2
void pushup(int id){
t[id].maxsize=
max({t[tol].maxsize,t[tor].maxsize,
t[tol].slize,t[tor].slize,
t[tol].srize,t[tor].srize,});
if(t[tol].rch!=t[tor].lch){
t[id].maxsize=max(t[id].maxsize,t[tol].srize+t[tor].slize);
}
if(t[tol].slize==t[tol].r-t[tol].l+1 and t[tol].rch!=t[tor].lch){
t[id].slize=t[tol].slize+t[tor].slize;
}
else{
t[id].slize=t[tol].slize;
}
if(t[tor].srize==t[tor].r-t[tor].l+1 and t[tol].rch!=t[tor].lch){
t[id].srize=t[tol].srize+t[tor].srize;
}
else{
t[id].srize=t[tor].srize;
}
t[id].lch=t[tol].lch;
t[id].rch=t[tor].rch;
}
void build(int id,int l,int r){
t[id].l=l;t[id].r=r;
if(l==r){
t[id].maxsize=t[id].slize=t[id].srize=1;
t[id].lch=t[id].rch=0;
return;
}
int mid(l,r);
build(tol,l,mid);
build(tor,mid+1,r);
pushup(id);
}
void change(int id,int p){
if(t[id].l==t[id].r){
int res=t[id].lch^1;
t[id].lch=t[id].rch=res;
return;
}
if(p<=t[tol].r) change(tol,p);
else change(tor,p);
pushup(id);
}
inline int ask(){
return t[1].maxsize;
}
}
int main(){
scanf("%d %d",&n,&q);
stree::build(1,1,n);
while(q--){
int x;
scanf("%d",&x);
stree::change(1,x);
printf("%d\n",stree::ask());
}
}
三元上升子序列
设 \(f2_i\) 表示以 \(i\) 结束的二元上升子序列个数，\(f3_i\) 表示以 \(i\) 结束的三元上升子序列个数，则不难有转移方程
\[f2_i=\sum_{\{j|j\lt i,a_j\lt a_i\}}1 \]\[f3_i=\sum_{\{j|j\lt i,a_j\lt a_i\}}f2_j \]对于内层的处理直接开一个值域线段树，从前到后在对应值域处插入答案，查询直接插 \(1\) 到当前值前缀和即可
因为有俩方程所以开了两颗线段树
要注意判当 \(a_i=1\) 时 \(a_i-1=0\) 的问题，我懒得判了直接全部都加一了，整体平移答案不变
不开 long long 见祖宗
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[30001];
int f2[30001],f3[30001];
int ans=0;
struct stree{
struct tree{
int l,r;
int sum;
}t[400001];
#define tol (id*2)
#define tor (id*2+1)
#define mid(l,r) mid=((l)+(r))/2
void build(int id,int l,int r){
t[id].l=l;t[id].r=r;
if(l==r){
return;
}
int mid(l,r);
build(tol,l,mid);
build(tor,mid+1,r);
}
void change(int id,int p,int val){
if(t[id].l==t[id].r){
t[id].sum+=val;
return;
}
if(t[tol].r>=p) change(tol,p,val);
else change(tor,p,val);
t[id].sum=t[tol].sum+t[tor].sum;
}
int ask(int id,int l,int r){
if(l<=t[id].l and t[id].r<=r){
return t[id].sum;
}
if(r<=t[tol].r){
return ask(tol,l,r);
}
else if(l>=t[tor].l){
return ask(tor,l,r);
}
int mid(t[id].l,t[id].r);
return ask(tol,l,mid)+ask(tor,mid+1,r);
}
};
stree x,y;
signed main(){
scanf("%d",&n);
x.build(1,1,100004);
y.build(1,1,100004);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);a[i]++;
}
for(int i=1;i<=n;++i){
ans+=y.ask(1,1,a[i]-1);
x.change(1,a[i],1);
y.change(1,a[i],x.ask(1,1,a[i]-1));
}
cout<<ans;
}