bzoj 2124 等差子序列 (线段树维护hash)

2124: 等差子序列

Time Limit: 3 Sec  Memory Limit: 259 MB
Submit: 1922  Solved: 714
[Submit][Status][Discuss]

Description

给一个1到N的排列{Ai},询问是否存在1<=p1<p2<p3<p4<p5<…<pLen<=N (Len>=3),
使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。
 

Input

输入的第一行包含一个整数T,表示组数。
下接T组数据,每组第一行一个整数N,每组第二行为一个1到N的排列,数字两两之间用空格隔开。
N<=10000,T<=7
 

Output

对于每组数据,如果存在一个等差子序列,则输出一行“Y”,否则输出一行“N”。
 

Sample Input

2
3
1 3 2
3
3 2 1

Sample Output

N
Y
 
思路:
 
线段树神仙操作。。完全想不到怎么用线段树写,看了别人题解看了一天才看懂这操作。。
题目要求存在个数不小于3的等差序列就行了,那么我们只要找到三个数可以组成等差序列就可以了。
我们先从1-n逐步插入,用01表示插入的状态吗如果插入了就标为1,然后只要找出当前值左右两边是否存在
距离相等但状态不同的点,如果有的话那么就存在这么一种等差序列,因为状态不同只有一种情况:一个之前
就已经插入了,一个还没插入,但另一个迟早会插入,所以我们不用管,只要找到这个就可以确定他是等差序列了。
用线段树维护一下hash就行了。
线段树维护的操作比较麻烦,主要就是将这个由01组成的序列由二进制转成10进制来保存,每一步都取下模,如果这
两个数的十进制不同,那他们的二进制肯定也不同。这样就可以判断出答案了。
 
实现代码;
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mid ll m = (l + r) >> 1
const ll M = 1e5+;
const ll md = 1e9+;
ll suml[M<<],sumr[M<<],a[M],pw[M];
void pushup(ll l,ll r,ll rt){
ll len = r - l + ;
ll m = len / ;
suml[rt] = (suml[rt<<]*pw[m]+suml[rt<<|])%md;
sumr[rt] = (sumr[rt<<|]*pw[len-m]+sumr[rt<<])%md;
return ;
} void update(ll p,ll l,ll r,ll rt){
if(l == r){
suml[rt] = sumr[rt] = ;
return ;
}
mid;
if(p <= m) update(p,lson);
else update(p,rson);
pushup(l,r,rt);
} ll queryl(ll L,ll R,ll l,ll r,ll rt){
if(L > R) return ;
if(L == l&&R == r) return suml[rt];
mid;
if(L > m) return queryl(L,R,rson);
else if(R <= m) return queryl(L,R,lson);
else return (queryl(L,m,lson)*pw[R-m]+queryl(m+,R,rson))%md;
} ll queryr(ll L,ll R,ll l,ll r,ll rt){
if(L > R) return ;
if(L == l&&R == r) return sumr[rt];
mid;
if(L > m) return queryr(L,R,rson);
else if(R <= m) return queryr(L,R,lson);
else return (queryr(L,m,lson)+queryr(m+,R,rson)*pw[m-L+])%md;
} int main()
{
ll t,n;
ios::sync_with_stdio();
cin.tie(); cout.tie();
cin>>t;
pw[] = ;
for(ll i = ;i <= ;i++)
pw[i] = (pw[i-]*)%md;
while(t--){
cin>>n;
memset(suml,,sizeof(suml));
memset(sumr,,sizeof(sumr));
memset(a,,sizeof(a));
ll flag = ;
for(ll i = ;i <= n;i ++) cin>>a[i];
for(ll i = ;i <= n;i ++){
ll len = min(a[i]-,n-a[i]);
ll t1 = queryl(a[i]-len,a[i]-,,n,);
ll t2 = queryr(a[i]+,a[i]+len,,n,);
if(t1!=t2){
flag = ;break;
}
update(a[i],,n,);
}
if(!flag) cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
}
上一篇:Linux知识要点大全(第一章)


下一篇:Windows DOS 窗口设置字体颜色