CERC2017I 题目是求最小的好区间 好区间就是一段区间都是连续的数 对于好区间显然有个数据结构叫析和树是可以求解的 但是我们用线段树怎么处理呢 首先我们知道 好区间 l 到 r是满足区间maxx-区间minn = r - l 然后我们又知道 两个好区间的交 一定也是好区间 反证法:假如这个交不是好区间 差几个数 那么这几个数如果在左边 那么和右边的数就不能构成好区间 所以两个好区间的交也一定是好区间 这样的话我们可以固定每个l不动 去右边找满足的最小的r(使得 l r包括询问区间) 用一个数组 tmp[i] 代表 i 后面有几个满足 那么 tmp[i] = r- i tmp[i]+i = r; 所以你让tmp[i] 一开始= i， 每次找线段树最大值是否等于 r 因为每个数只有对相邻的数有贡献 而且我们是从前往后统计 所以代码有这句话
if(arr[i]>1&&p[arr[i]-1]<=i) sgt::update(1,1,n,1,p[arr[i]-1],1); if(arr[i]<n&&p[arr[i]+1]<=i) sgt::update(1,1,n,1,p[arr[i]+1],1); /* created by ljq */ #include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <cmath> #include <map> #include <stack> #include <set> #include <sstream> #include <vector> #include <stdlib.h> #include <algorithm> //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //#pragma comment(linker, "/STACK:10240000,10240000") using namespace std; #define dbg(x) cout<<#x<<" = "<< (x)<< endl #define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl #define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) typedef pair<int,int> pll; typedef long long ll; typedef unsigned long long ull; const ull hash1 = 201326611; const int inf = 0x3f3f3f3f; const int _inf = 0xc0c0c0c0; const ll INF = 0x3f3f3f3f3f3f3f3f; const ll _INF = 0xc0c0c0c0c0c0c0c0; const ll mod = (int)1e9+7; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;} ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);} void exgcd(ll a,ll b,ll &x,ll &y,ll &d){if(!b) {d = a;x = 1;y=0;}else{exgcd(b,a%b,y,x,d);y-=x*(a/b);}}//printf("%lld*a + %lld*b = %lld\n", x, y, d); //ull ha[MAX_N],pp[MAX_N]; inline int read() { int date = 0,m = 1; char ch = 0; while(ch!='-'&&(ch<'0'|ch>'9'))ch = getchar(); if(ch=='-'){m = -1; ch = getchar();} while(ch>='0' && ch<='9') { date = date*10+ch-'0'; ch = getchar(); }return date*m; } /*int root[MAX_N],cnt,sz; namespace hjt { #define mid ((l+r)>>1) struct node{int l,r,maxx;}T[MAX_N*40]; #undef mid }*/ const int MAX_N = 100025; vector<pair<int ,int > >vt[MAX_N]; priority_queue<pair<int ,int > > q; int Max(int a,int b){if(a>b)return a;return b;} namespace sgt { #define mid ((l+r)>>1) int pos[MAX_N<<2],maxx[MAX_N<<2],col[MAX_N<<2]; void up(int rt) { if(maxx[rt<<1]>maxx[rt<<1|1]) { pos[rt] = pos[rt<<1]; maxx[rt] = maxx[rt<<1]; } else { pos[rt] = pos[rt<<1|1]; maxx[rt] = maxx[rt<<1|1]; } } void build(int rt,int l,int r) { col[rt] = 0; if(l==r) { maxx[rt] = pos[rt] = l; return; } build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); up(rt); } void down(int rt,int l,int r) { if(col[rt]) { col[rt<<1]+=col[rt]; col[rt<<1|1]+=col[rt]; maxx[rt<<1]+=col[rt]; maxx[rt<<1|1]+=col[rt]; col[rt] = 0; } } void update(int rt,int l,int r,int x,int y,int v) { if(x<=l&&r<=y) { maxx[rt]+=v; col[rt]+=v; return; } down(rt,l,r); if(x>mid) update(rt<<1|1,mid+1,r,x,y,v); else if(y<=mid) update(rt<<1,l,mid,x,y,v); else update(rt<<1,l,mid,x,y,v),update(rt<<1|1,mid+1,r,x,y,v); up(rt); } pair<int,int> query(int rt,int l,int r,int x,int y) { if(x<=l&&r<=y) { return make_pair(maxx[rt],pos[rt]); } down(rt,l,r); if(x>mid) return query(rt<<1|1,mid+1,r,x,y); else if(y<=mid) return query(rt<<1,l,mid,x,y); else return max(query(rt<<1,l,mid,x,y),query(rt<<1|1,mid+1,r,x,y)); } #undef mid } int n,arr[MAX_N],p[MAX_N]; pair<int,int > ans[MAX_N]; bool judge(pair<int,int > top,int xb) { pair<int ,int > tmp = sgt::query(1,1,n,1,top.first); if(tmp.first==xb) { ans[top.second] = make_pair(tmp.second,tmp.first); return true; } return false; } int main() { //ios::sync_with_stdio(false); //freopen("a.txt","r",stdin); //freopen("b.txt","w",stdout); int m,a,b; scanf("%d",&n); for(int i = 1;i<=n;++i) scanf("%d",&arr[i]),p[arr[i]] = i; sgt::build(1,1,n); scanf("%d",&m); for(int i = 1;i<=m;++i) { scanf("%d%d",&a,&b); vt[b].push_back(make_pair(a,i)); } for(int i = 1;i<=n;++i) { if(arr[i]>1&&p[arr[i]-1]<=i) sgt::update(1,1,n,1,p[arr[i]-1],1); if(arr[i]<n&&p[arr[i]+1]<=i) sgt::update(1,1,n,1,p[arr[i]+1],1); for(int j = 0;j<vt[i].size();++j) { q.push(make_pair(vt[i][j].first,vt[i][j].second)); } while(!q.empty()) { if(judge(q.top(),i)) q.pop(); else break; } } for(int i = 1;i<=m;++i) { printf("%d %d\n",ans[i].first,ans[i].second); } //fclose(stdin); //fclose(stdout); //cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl; return 0; }