noi.ac 257 B-白红宇

noi.ac 257 B

阅读量：5083 次

发布时间：2019-06-13

本文共 2697 字，大约阅读时间需要 8 分钟。

题目

　　区间[l,r]是连续满足，[l,r]中的数字的权值区间是一段连续的。多次询问可以完包含一个区间的连续区间。区间长度尽量小，如果有多个输出左端点靠左的。

分析：

　　[l,r]区间是连续的，当且仅当区间内有(r-l)*2个相邻的关系，即(2,3)，(6,5)都是相邻关系。那么将询问离线，不断维护左端点到当前点的区间内的相邻关系的数量。

　　即当前点是i，那么如果pos[a[i]-1]<=i的话，在1~pos[a[i]-1]这些位置+1，表示从这些位置到i的区间，增加一个相邻关系。

　　如果一个点j开始到i的相邻关系的数量等于(i-j)，那么说明(j~i)区间是连续区间，这里两个相邻关系只算了一个。所以初始时在每个位置增加数字下标即可。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #define pa pair
               
                using namespace std;typedef long long LL;inline LL read() { LL x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;}const int N = 100005;pa T[N << 2];int tag[N << 2], pos[N], a[N], ans1[N], ans2[N], n;set< pa > s;vector< pa > q[N];pa operator + (pa A, pa B) { return A.first > B.first ? A : B; }inline void col(int x,int y) { T[x].first += y, tag[x] += y; }inline void pushdown(int rt) { col(rt << 1, tag[rt]); col(rt << 1 | 1, tag[rt]); tag[rt] = 0; }void build(int l,int r,int rt) { if (l == r) { T[rt] = pa(l, l); return ; } int mid = (l + r) >> 1; build(l, mid, rt << 1); build(mid + 1, r, rt << 1 | 1); T[rt] = T[rt << 1] + T[rt << 1 | 1];}void update(int l,int r,int rt,int L,int R) { if (L <= l && r <= R) { T[rt].first ++, tag[rt] ++; return ; } int mid = (l + r) >> 1; if (tag[rt]) pushdown(rt); if (L <= mid) update(l, mid, rt << 1, L, R); if (R > mid) update(mid + 1, r, rt << 1 | 1, L, R); T[rt] = T[rt << 1] + T[rt << 1 | 1];}pa query(int l,int r,int rt,int L,int R) { if (L <= l && r <= R) return T[rt]; if (tag[rt]) pushdown(rt); int mid = (l + r) >> 1; if (R <= mid) return query(l, mid, rt << 1, L, R); else if (L > mid) return query(mid + 1, r, rt << 1 | 1, L, R); else return query(l, mid, rt << 1, L, R) + query(mid + 1, r, rt << 1 | 1, L, R);}bool check(pa x,int i) { pa now = query(1, n, 1, 1, -x.first); if (now.first == i) { ans1[x.second] = now.second, ans2[x.second] = i; return 1; } return 0;}int main() { n = read(); for (int i = 1; i <= n; ++i) a[i] = read(), pos[a[i]] = i; int m = read(); for (int i = 1; i <= m; ++i) { int l = read(), r = read(); q[r].push_back(pa(-l, i)); } build(1, n, 1); for (int i = 1; i <= n; ++i) { for (int j = 0; j < (int)q[i].size(); ++j) s.insert(q[i][j]); if (a[i] > 1 && pos[a[i] - 1] <= i) update(1, n, 1, 1, pos[a[i] - 1]); if (a[i] < n && pos[a[i] + 1] <= i) update(1, n, 1, 1, pos[a[i] + 1]); while (!s.empty()) if (check(*s.begin(), i)) s.erase(s.begin()); else break; } for (int i = 1; i <= m; ++i) printf("%d %d\n", ans1[i], ans2[i]); return 0;}

转载于:https://www.cnblogs.com/mjtcn/p/10549149.html

你可能感兴趣的文章