試験線分樹二分+単点修正+区間照会

Problem I
Mex({al,al+1,al+2,...,ar}を定義します.その中の最小未出現の自然数です.
長いnのシーケンスa 1,a 2,a 3,…,anを与える.
すべての区間[L,R]のMex値の合計を求めます.
最初の行は整数n(1<=n<=1 e 5)を含みます.
2行目はn個の整数を含み、a 1,a 2,…,an(1<=ai<=1 e 5)を表します.
出力Mex値の和
Sample Input
5
1 0 2 0 1
Sample Output
24
試験の時はAさんが落としましたが、局の私の線分樹の二分はとても頭が悪くて、とても綺麗ではないので、まとめてみる必要があると思います.
実は私は一つの事実を無視しました.秩序ある数列の中で二分の時に、右区間の最大値を知るだけで次の方向が分かります.他の値を使う必要はありません.だからもう一つの区間の最大値を維持するだけで二点になります.私のコードもこのようにします.ただ前に何かわけのわからない変なものが入っています.私も脳障害か何かの鬼かは分かりません.つまり、次は間違えないようにしてください.
この問題については、自分では何もいいことはないと思います.規則を示してから出てきます.あとはあなたの造化を見ます.
私の(変なものをメンテナンスしたので、長く見えて嫌です.)

#include
#include
#include
#define ll long long
#define maxn 100020
#define ls u<<1,l,mid
#define rs u<<1|1,mid+1,r
using namespace std;
void init(){
	freopen("A.in","r",stdin);
	freopen("A.out","w",stdout);
}
int n,cur[maxn],front[maxn];
bool vis[maxn];

struct node{
	int l,r,sum,add,rMin,rMax,lMin,lMax,lazy;
}nod[maxn*4];
int head[maxn],last[maxn],tot=1;
struct dege{
	int v,next;
}e[maxn*2];
void adde(int a,int b){
	e[tot].v=b;
	e[tot].next=head[a];
	head[a]=tot++;
}

void push_up(int u){
	nod[u].sum=nod[u<<1].sum+nod[u<<1|1].sum;
	nod[u].rMin=nod[u<<1|1].lMin;nod[u].lMax=nod[u<<1].rMax;
	nod[u].rMax=nod[u<<1|1].rMax,nod[u].lMin=nod[u<<1].lMin;
}
void push_down(int u){
	if(nod[u].lazy==0)return;
	int add=nod[u].add;
	nod[u<<1].add=nod[u<<1|1].add=add;
	nod[u<<1].lazy=nod[u<<1|1].lazy =1;
	
	nod[u<<1].sum=(nod[u<<1].r-nod[u<<1].l+1)*add;
	nod[u<<1|1].sum=(nod[u<<1|1].r-nod[u<<1|1].l+1)*add;
	
	nod[u<<1].rMax=nod[u<<1].rMin=nod[u<<1].lMin=nod[u<<1].lMax=add;
	nod[u<<1|1].rMax=nod[u<<1|1].rMin=nod[u<<1|1].lMin=nod[u<<1|1].lMax=add;
	
	nod[u].add=0;
	nod[u].lazy=0;
}

void build(int u,int l,int r){
	nod[u].l=l,nod[u].r=r;
	if(l==r){
		nod[u].lMin=nod[u].lMax=nod[u].rMin=nod[u].rMax=nod[u].sum=front[l];
		nod[u].add=nod[u].lazy=0;
		return ;
	}
	int mid=l+r>>1;
	build(ls);build(rs);
	push_up(u);
}

int query_max(int u,int l,int r,int x){
	if(l==r)return r;
	push_down(u);
	push_up(u);
	int mid=l+r>>1,rr=u<<1|1;
	if(nod[u<<1].rMax<=x)return query_max(rs,x);
	if(nod[u<<1].rMax>x)return query_max(ls,x);
}

void update(int u,int l,int r,int x,int y,int add){
	if(x==l&&r==y){
		nod[u].sum=(r-l+1)*add;
		nod[u].add=add;
		nod[u].lazy=1;
		nod[u].rMax=nod[u].rMin=nod[u].lMin=nod[u].lMax=add;
		return;
	}
	push_down(u);
	int mid=l+r>>1;
	if(x>mid)update(rs,x,y,add);
	else if(y<=mid)update(ls,x,y,add);
	else{
		update(ls,x,mid,add);
		update(rs,mid+1,y,add);
	}
	push_up(u);
}

int query_z(int u,int l,int r,int x){
	if(l==r)return nod[u].sum ;
	push_down(u);
	int mid=l+r>>1;
	if(x>mid)return query_z(rs,x);
	else return query_z(ls,x);
}


int main(){
	init();
	memset(head,-1,sizeof(head));
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",cur+i);
		if(!last[cur[i]])last[cur[i]]=i;
		else{
			adde(last[cur[i]],i);
			last[cur[i]]=i;
		}
	}
	int last=0;
	for(int i=1;i<=n;i++){
		vis[cur[i]]=true;
		while(vis[last])last++;
		front[i]=last;
	}
	ll ans=0;
	
	build(1,1,n);
	
	for(int i=1;i

改善されたのですが、私のようなスペースが空飛ぶコードの前にはまだ長いですが、煩雑ではありません.

#include
#include
#include
#define ll long long
#define maxn 100020
#define ls u<<1,l,mid
#define rs u<<1|1,mid+1,r
using namespace std;
void init(){
	freopen("A.in","r",stdin);
	freopen("A.out","w",stdout);
}
int n,cur[maxn],front[maxn];
bool vis[maxn];

struct node{
	int l,r,sum,add,Max,lazy;
}nod[maxn*4];
int head[maxn],last[maxn],tot=1;
struct dege{
	int v,next;
}e[maxn*2];
void adde(int a,int b){
	e[tot].v=b;
	e[tot].next=head[a];
	head[a]=tot++;
}

void push_up(int u){
	nod[u].sum=nod[u<<1].sum+nod[u<<1|1].sum;
	nod[u].Max=max(nod[u<<1].Max,nod[u<<1|1].Max);
}
void push_down(int u){
	if(nod[u].lazy==0)return;
	int add=nod[u].add;
	nod[u<<1].add=nod[u<<1|1].add=add;
	nod[u<<1].lazy=nod[u<<1|1].lazy =1;
	
	nod[u<<1].sum=(nod[u<<1].r-nod[u<<1].l+1)*add;
	nod[u<<1|1].sum=(nod[u<<1|1].r-nod[u<<1|1].l+1)*add;
	
	nod[u<<1].Max=add;
	nod[u<<1|1].Max=add;
	
	nod[u].add=0;nod[u].lazy=0;
}

void build(int u,int l,int r){
	nod[u].l=l,nod[u].r=r;
	if(l==r){
		nod[u].Max=nod[u].sum=front[l];
		nod[u].add=nod[u].lazy=0;
		return ;
	}
	int mid=l+r>>1;
	build(ls);build(rs);
	push_up(u);
}

int query_max(int u,int l,int r,int x){
	if(l==r)return nod[u].sum>x?l:l+1;
	push_down(u);
	int mid=l+r>>1;
	if(nod[u<<1].Max<=x)return query_max(rs,x);
	if(nod[u<<1].Max>x)return query_max(ls,x);
}

void update(int u,int l,int r,int x,int y,int add){
	if(x==l&&r==y){
		nod[u].sum=(r-l+1)*add;
		nod[u].add=add;nod[u].lazy=1;
		nod[u].Max=add;
		return;
	}
	push_down(u);
	int mid=l+r>>1;
	if(x>mid)update(rs,x,y,add);
	else if(y<=mid)update(ls,x,y,add);
	else update(ls,x,mid,add),update(rs,mid+1,y,add);
	push_up(u);
}

int main(){
	init();
	memset(head,-1,sizeof(head));
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",cur+i);
		if(!last[cur[i]])last[cur[i]]=i;
		else{
			adde(last[cur[i]],i);
			last[cur[i]]=i;
		}
	}
	int last=0;
	for(int i=1;i<=n;i++){
		vis[cur[i]]=true;
		while(vis[last])last++;
		front[i]=last;
	}
	ll ans=0;
	build(1,1,n);
	for(int i=1;i