尽量简洁。
CF679E
不难发现直接赋值和修改的时间是对的,所以讲一下写法。把将区间变为好数的操作称为加。
对于一个已经进行过区间赋值的区间打一个标记 Up,那么这个区间及其子区间可看作1个点,那么修改的复杂度就跟单点修改是一样的了。
因此对于加操作可以这么写
void do2(int p,ll va){
if(t[p].up){
t[p].dif-=va;t[p].mi=t[p].dif;
while(t[p].dif<0){t[p].dif+=fra[t[p].up+1]-fra[t[p].up];t[p].up++;t[p].mi=t[p].dif;}
}
else t[p].mi-=va,t[p].laz+=va;
return;
}
按时间顺序维护位置比较难做,因为修改的值没有特殊性。
从问题中后缀这个要求入手。
发现如果按位置从后往前,线段树的节点维护当前时间后缀最小值 mx,数量 cnt(如叶子节点1表示1时刻的后缀最小值),
可以发现一个区间的 mx 改变时 cnt++,于是使用无区间加吉司机线段树维护即可。
complete code
CF1588F
对于交换操作,可能合成环或拆开环,导致线段树比较难维护。所以我们考虑根号复杂度的方法。
设我们每 B 个操作进行一次处理。
我们把二操作和三操作的点设为关键点,将一个关键点到下一个关键点中间的链压缩为一个节点,则总节点数在 B 数量级。
对于二操作,一次是 B 数量级。把 B 设为 \(\sqrt{n}\) 即可。
complete code
CUTPLANT
我们称剪后花的高度为 B,剪前花的高度为 A,按 B 从小到大处理,可以发现当两个相同的 B 之间若 maxB<=B 且 minA>=B,则这次剪花可以一起完成。
线段树维护一下即可。
#include<cstdio>
#include<iostream>
#include<algorithm>
#pragma GCC optimize(3,"inline","Ofast")
using namespace std;
const int INF=2e9;
const int MAXN=1e5+5;
typedef pair<int,int> kk;
struct SG{
int b,id;
}ren[MAXN];
int T,ans,n,a[MAXN],t1[MAXN<<3],t2[MAXN<<3];bool pd;
bool cmp(SG xx,SG yy){return xx.b==yy.b?xx.id<yy.id:xx.b<yy.b;}
void pup(int p){t1[p]=min(t1[p<<1],t1[p<<1|1]);t2[p]=max(t2[p<<1],t2[p<<1|1]);}
void build(int p,int l,int r){
if(l==r){t1[p]=a[l];t2[p]=ren[l].b;return;}
int mid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);pup(p);
}
kk que(int p,int L,int R,int l,int r){
if(l>R||r<L)return kk(INF,-INF);
else if(l>=L&&r<=R){return kk(t1[p],t2[p]);}
else{
kk xx,yy;int mid=(l+r)>>1;
xx=que(p<<1,L,R,l,mid);yy=que(p<<1|1,L,R,mid+1,r);
return kk(min(xx.first,yy.first),max(xx.second,yy.second));
}
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);ans=0;pd=0;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
scanf("%d",&ren[i].b);ren[i].id=i;
if(ren[i].b>a[i]){pd=1;}
}
if(pd){printf("-1\n");continue;}
build(1,1,n);sort(ren+1,ren+1+n,cmp);
for(int i=1;i<=n;i++){
int j=i,B=ren[i].b;int tmp=0;
while(ren[j+1].b==ren[j].b){j++;if(j==n) break;}
for(int k=i;k<=j;k++){
if(tmp==0) tmp=(a[ren[k].id]==ren[k].b)?0:1;
else{
kk ttt=que(1,ren[k-1].id,ren[k].id,1,n);
if(ttt.first>=B&&ttt.second<=B) continue;
else ans++,tmp=(a[ren[k].id]==ren[k].b)?0:1;
}
}
if(tmp) ans++;
i=j;
}
printf("%d\n",ans);
}
return 0;
}
想想为什么 b 是一个排列并且每次只加1,发现我们记录区间 minb 和 maxa,当 maxa>minb 时单点修改即可。
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5;
int n,m,b[MAXN];
void read(int &x){
x=0;
int f=1;
char s=getchar();
while(s<'0'||s>'9'){
if(s=='-') f=-1;
s=getchar();
}
while(s>='0'&&s<='9'){
x=(x<<3)+(x<<1)+(s^48);s=getchar();
}
x*=f;
}
char s[10];
struct SG{
struct tree{
int ma,sum,ta,mb;
}t[MAXN<<2];
void pup(int p){
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
t[p].ma=max(t[p<<1].ma,t[p<<1|1].ma);
t[p].mb=min(t[p<<1].mb,t[p<<1|1].mb);
return;
}
void pdo(int p){
if(!t[p].ta) return;
t[p<<1].ma+=t[p].ta;t[p<<1|1].ma+=t[p].ta;t[p<<1].ta+=t[p].ta;t[p<<1|1].ta+=t[p].ta;t[p].ta=0;
}
void bui(int p,int l,int r){
t[p].sum=0;t[p].ma=0;t[p].ta=0;
if(l==r){
t[p].mb=b[l];return;
}
int mid=l+r>>1;
bui(p<<1,l,mid);bui(p<<1|1,mid+1,r);pup(p);
}
void upd(int p,int ql,int qr,int l,int r){
if(l>=ql&&r<=qr){
t[p].ma++;
if(t[p].ma<t[p].mb){
t[p].ta++;return;
}
if(l==r&&t[p].ma>=t[p].mb){
t[p].mb+=b[l];t[p].sum++;return;
}
}
pdo(p);
int mid=l+r>>1;
if(ql<=mid) upd(p<<1,ql,qr,l,mid);
if(qr>mid) upd(p<<1|1,ql,qr,mid+1,r);
pup(p);
}
int que(int p,int ql,int qr,int l,int r){
if(l>=ql&&r<=qr){return t[p].sum;}
pdo(p);
int mid=l+r>>1,res=0;
if(ql<=mid) res+=que(p<<1,ql,qr,l,mid);
if(qr>mid) res+=que(p<<1|1,ql,qr,mid+1,r);
return res;
}
}T;
int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;i++) read(b[i]);
T.bui(1,1,n);
while(m--){
scanf("%s",s+1);
if(s[1]=='a'){
int l,r;read(l);read(r);T.upd(1,l,r,1,n);
}
else{
int l,r;read(l);read(r);printf("%d\n",T.que(1,l,r,1,n));
}
}
}
return 0;
}
0,1赋成-1,1,将相邻前缀和的值连边,不难看出一次操作是将一个环的边反向,那么直接把图看成无向图,每次通过判断 now 和 now-1 的出边数量决定走的方向即可。
UOJ164
对于这类没有区间和的历史最值问题我们可以定义一个标记 (a,b) 表示 x=max(x+a,b)。
在进行修改时对标记进行合并和取 max 即可。
注意:标记之间没有交换律!
complete code