【TIOJ 1169】氣球博覽會

原題連結：http://tioj.infor.org/problems/1169

首先要先想到第三子題怎麼做
對於每一個顏色，都開一棵線段樹
對於一個顏色K的線段樹維護：
1.從左邊開始不含K的最長區間
2.從右邊開始不含K的最長區間
3.這個區間不含K的最長區間
維護並不難想也不難寫，總複雜度O(2^cN+QlgN)，空間複雜度O(2^CN)

問題在當C到24時，不管是時間還是空間都有問題
我們首先觀察到，在尚未有任何氣球的時候，對於每個顏色的線段樹長相都一樣
先把原序列當成N個的單點修改操作，這樣每個修改操作一定只會到動到lgN個線段樹的節點
那這裡就可以用動態開點的方式，如果記憶體是空的表示這個區間絕對沒有該顏色，可以直接把答案填滿，這樣也不用預處理2^cN。
至於詢問操作就照原本的寫，只要注意不要讀到空的記憶體就好了
複雜度O((N+Q)lgN)，空間上如果對顏色離散化或用map會更好，不過我是直接硬開2^24個指標就是了XD

	#pragma GCC optimize("Ofast")
	#include <bits/stdc++.h>
	#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	#define ll long long
	#define pb push_back
	#define MEM(i,j) memset(i,j,sizeof i)
	#define F first
	#define S second
	#define ET cout << "\n"
	#define DB(a,s,e) {for(int i=s;i<e;i++) cout << a[i] << " ";ET;}
	using namespace std;
	int N,Q,C,num[200000];
	struct mode
	{
	int Left,Right,ans;
	void reset(int k)
	{
	Left=Right=ans=k;
	}
	};
	struct node
	{
	mode data;
	node *l,*r;
	void reset(int k)
	{
	data.reset(k),l=r=0;
	}
	void pull(int lz,int rz)
	{
	if(!l && !r) data.reset(lz+rz);
	if(l && !r)
	{
	if(l->data.Left==lz) data.Left=lz+rz;
	else data.Left=l->data.Left;
	data.ans=max(l->data.Right+rz,l->data.ans),data.Right=l->data.Right+rz;
	}
	if(r && !l)
	{
	if(r->data.Right==rz) data.Right=lz+rz;
	else data.Right=r->data.Right;
	data.ans=max(r->data.Left+lz,r->data.ans),data.Left=r->data.Left+lz;
	}
	if(l && r)
	{
	data.ans=max(l->data.Right+r->data.Left,max(l->data.ans,r->data.ans));
	if(l->data.Left==lz) data.Left=r->data.Left+lz;
	else data.Left=l->data.Left;
	if(r->data.Right==rz) data.Right=l->data.Right+rz;
	else data.Right=r->data.Right;
	}
	}
	}*head[16777216];
	node* insert(int a,int l,int r,node *p,int type)
	{
	if(!p) p=new node,p->reset(r-l+1);
	if(l==r)
	return p->data.reset(type),p;
	int m=(l+r)/2;
	if(a<=m) p->l=insert(a,l,m,p->l,type);
	else p->r=insert(a,m+1,r,p->r,type);
	return p->pull(m-l+1,r-m),p;
	}
	mode query(int L,int R,int l,int r,node *p)
	{
	if(L<=l && R>=r)
	if(!p) return mode{r-l+1,r-l+1,r-l+1};
	else return p->data;
	int m=(l+r)/2;
	mode a,b,re;
	a.reset(0),b.reset(0);
	if(L<=m) a=query(L,R,l,m,(p ? p->l : 0));
	if(R>m)
	{
	b=query(L,R,m+1,r,(p ? p->r : 0));
	if(L>m)
	re=b;
	else
	{
	re.ans=max(a.Right+b.Left,max(a.ans,b.ans));
	if(a.Left==m-l+1) re.Left=a.Left+b.Left;
	else re.Left=a.Left;
	if(b.Right==r-m) re.Right=b.Right+a.Right;
	else re.Right=b.Right;
	}
	}
	else re=a;
	return re;
	}
	int main()
	{jizz
	int i,l,r,k,t;
	cin >> N >> Q >> C;
	for(i=0;i<N;i++)
	cin >> num[i],head[num[i]]=insert(i,0,N-1,head[num[i]],0);
	while(Q--)
	{
	cin >> t;
	if(!t)
	cin >> l >> k,head[num[l]]=insert(l,0,N-1,head[num[l]],1),num[l]=k,head[num[l]]=insert(l,0,N-1,head[num[l]],0);
	else
	cin >> l >> r >> k,r--,cout << query(l,r,0,N-1,head[k]).ans << "\n";
	}
	}

view raw tioj1169.cpp hosted with ❤ by GitHub