JXOI2017颜色解题报告

JXOI2017颜色

• 首先记录每个位置上颜色在序列中上次出现的位置
• 开两颗线段树&＃xff0c;第一棵维护区间最大值&＃xff0c;实际上是维护当前必须被删去的颜色的位置的最大值&＃xff0c;第二棵则是维护区间和
• 首先倒着扫一遍&＃xff0c;对于当前颜色的后面一个颜色&＃xff0c;将其删去&＃xff0c;那他的\(pre\)肯定也要删去&＃xff0c;将其\(pre\)的位置加入第一棵线段树&＃xff0c;对每个位置记一个\(able\)&＃xff0c;值为当前第一棵线段树中最大值&＃xff0c;表示当前点到\(able&＃43;1\)这一段区间都是可以的。
• 初始化第二颗树&＃xff0c;\(sum\)值初始设为1&＃xff0c;对于每个位置&＃xff0c;如果他有前驱&＃xff0c;那他与他前驱中这段的颜色不能计入答案&＃xff0c;将其全部设为0&＃xff0c;统计\(i\)到\(able&＃43;1\)的值即可。

// luogu-judger-enable-o2
#include
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i&＃61;(sign)a;i<&＃61;(sign)b;&＃43;&＃43;i)
#define Fordown(i,a,b) for(register sign i&＃61;(sign)a;i>&＃61;(sign)b;--i)
const int N&＃61;3e5&＃43;5;
bool cmax(sign &a,sign b){return (abool cmin(sign &a,sign b){return (a>b)?a&＃61;b,1:0;}
templateinline T read()
{T f&＃61;1,ans&＃61;0;char ch&＃61;getchar();while(!isdigit(ch)&&ch!&＃61;&＃39;-&＃39;)ch&＃61;getchar();if(ch&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1,ch&＃61;getchar();while(isdigit(ch))ans&＃61;(ans<<3)&＃43;(ans<<1)&＃43;(ch-&＃39;0&＃39;),ch&＃61;getchar();return ans*f;
}
templateinline void write(T x,char y)
{if(x&＃61;&＃61;0){putchar(&＃39;0&＃39;);putchar(y);return;}if(x<0){putchar(&＃39;-&＃39;);x&＃61;-x;}static char wr[20];int top&＃61;0;for(;x;x/&＃61;10)wr[&＃43;&＃43;top]&＃61;x%10&＃43;&＃39;0&＃39;;while(top)putchar(wr[top--]);putchar(y);
}
void file()
{#ifndef ONLINE_JUDGEfreopen("4056.in","r",stdin);freopen("4056.out","w",stdout);#endif
}
#define lson h<<1,l,mid
#define rson h<<1|1,mid&＃43;1,r
namespace T1
{int maxn[N<<2];void build(int h,int l,int r){maxn[h]&＃61;0;if(l&＃61;&＃61;r)return;int mid&＃61;(l&＃43;r)>>1;build(lson);build(rson);}void update(int h,int l,int r,int pos,int v){if(l&＃61;&＃61;r){maxn[h]&＃61;v;return;}int mid&＃61;(l&＃43;r)>>1;if(pos<&＃61;mid)update(lson,pos,v);else update(rson,pos,v);maxn[h]&＃61;max(maxn[h<<1],maxn[h<<1|1]);}
}
namespace T2
{int sum[N<<2],lazy[N<<2];void push_down(int h){if(!lazy[h])return;int ls&＃61;h<<1,rs&＃61;ls|1;lazy[ls]&＃61;lazy[rs]&＃61;1;sum[ls]&＃61;sum[rs]&＃61;0;lazy[h]&＃61;0;}void build(int h,int l,int r){sum[h]&＃61;1;lazy[h]&＃61;0;if(l&＃61;&＃61;r)return;int mid&＃61;(l&＃43;r)>>1;build(lson);build(rson);sum[h]&＃61;sum[h<<1]&＃43;sum[h<<1|1];}void update(int h,int l,int r,int s,int t){if(s<&＃61;l&&r<&＃61;t){sum[h]&＃61;0;lazy[h]&＃61;1;return;}push_down(h);int mid&＃61;(l&＃43;r)>>1;if(s<&＃61;mid)update(lson,s,t);if(mid>1;if(s<&＃61;mid)res&＃61;query(lson,s,t);if(mid}
ll ans;
int n,m,a[N];
int pos[N],pre[N],able[N];
void input()
{n&＃61;read();For(i,1,n){a[i]&＃61;read();cmax(m,a[i]);pre[i]&＃61;pos[a[i]];pos[a[i]]&＃61;i;}
}
void init()
{m&＃61;0;ans&＃61;0;memset(pos,0,sizeof pos);memset(able,0,sizeof able);memset(pre,0,sizeof pre);
}
void work()
{T1::build(1,1,m);T2::build(1,1,n);Fordown(i,n,1){if(i}
int main()
{file();int T&＃61;read();while(T--){init();input();work();}return 0;
}