題目連結
There are n men ,every man has an ID(1..n).their ID is unique. Whose ID is i and i-1 are friends, Whose ID is i and i+1 are friends. These n men stand in line. Now we select an interval of men to make some group. K men in a group can create K*K value. The value of an interval is sum of these value of groups. The people of same group's id must be continuous. Now we chose an interval of men and want to know there should be how many groups so the value of interval is max.
Input
First line is T indicate the case number.
For each case first line is n, m(1<=n ,m<=100000) indicate there are n men and m query.
Then a line have n number indicate the ID of men from left to right.
Next m line each line has two number L,R(1<=L<=R<=n),mean we want to know the answer of [L,R].
Output
For every query output a number indicate there should be how many group so that the sum of value is max.
Sample Input
1
5 2
3 1 2 5 4
1 5
2 4 Sample Output
1
2 題意：現在有n個數，編号1到n，但是它們不是按順序排列，現在有m次詢問，每次詢問給出個(l,r)；問在這個區間内連續的塊有多少個，單個也算連續。拿樣例解釋一下：3 1 2 5 4，第二次詢問(2,4)。這個區間的數有（1 2 5）可以分成(1,2),(5)兩個塊。是以第二次詢問答案為2。
題解：首先我們将所有的查詢區間全部按照右端點排序，排完序然後從左到右依次查詢。我們用一個sum數組來記錄（sum[i]表示1-i可以分成多少塊）pos數組存num[i]的位置。現在我們就要用樹狀數組為維護了。首先題中說數字i和i-1,i+1都是相連的。我們現在假設目前i出現的區間i-1,i+1都未出現，是以我們直接用樹狀數組維護+1。現在就要考慮兩邊的數出現在目前區間了，要是num[i]+1出現在目前區間，我們就需要在num[i]+1的位置用樹狀數組維護全部-1.因為兩個數在一個區間的話，說明兩個數可以合成一個塊，現在兩個位置都因之前的假設全部都加了1，現在兩個可以合成一個塊，是以其中一個的位置上要-1。num[i]-1的情況和num[i]+1相同，要是判斷在目前區間，直接用樹狀數組維護。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn=1e5+10;
const int mod=1e9+7;
const int inf=1e8;
#define me(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
#define mid (l+r)/2
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef long long ll;
using namespace std;
int sum[maxn],n,m;
struct node
{
int l,r,i;
bool friend operator<(node a,node b)
{
return a.r<b.r;
}
}a[maxn];
int get_sum(int x)
{
int ans=0;
while(x)
{
ans+=sum[x];
x-=lowbit(x);
}
return ans;
}
void add(int i,int x)
{
while(i<=n)
{
sum[i]+=x;
i+=lowbit(i);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int num[maxn],pos[maxn],ans[maxn];
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
pos[num[i]]=i;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
a[i].i=i;
}
sort(a+1,a+m+1);
me(sum,0);
int j=1;
for(int i=1;i<=n;i++)
{
add(i,1);
if(num[i]<n&&pos[num[i]+1]<i)//處理目前數的後一個數
add(pos[num[i]+1],-1);
if(num[i]>1&&pos[num[i]-1]<i)//處理目前數的前一個數
add(pos[num[i]-1],-1);
while(j<=n&&a[j].r==i)///這就是為啥區間要按照r從小到大排序.
{
ans[a[j].i]=get_sum(a[j].r)-get_sum(a[j].l-1);
j++;
}
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
return 0;
}