2015
09-17

# Group

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.

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].

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].

1
5 2
3 1 2 5 4
1 5
2 4

1
2

离线处理每个查询，遍历每个点，设当前处理的区间终点为R，处理每个查询的时候，首先假设所有的数a[i]都是自己独立成段，如果有a[i]+1,或者a[i]-1的数在区间[L,R]内，那么它肯定不是独立成段的，也就是我们要减去在[L,R]内不独立成段的数的个数。问题就转化为查询[L,R]之前不独立成段的数的个数。可以这样处理，对于a[i]，如果发现a[i]-1，或者a[i]+1的位置，在[1,R]之间，那么我们在相应位置加上1，直接查询区间[L,R]内有多少1就可以了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <algorithm>
#include <queue>
#define INF (1<<30)
#define clearAll(a)  memset(a,0,sizeof(a))
#define sq(a) ((a)*(a))

#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(a,b) (a+((b-a)>>1))

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const int N=100005;

struct node
{
int cnt[N*4];
void PushDown(int ind)
{
if(cnt[ind])
{
cnt[LL(ind)]+=cnt[ind];
cnt[RR(ind)]+=cnt[ind];
cnt[ind]=0;
}
}
void build(int lft,int rht,int ind)
{
cnt[ind]=0;
if(lft!=rht)
{
int mid=MID(lft,rht);
build(lft,mid,LL(ind));
build(mid+1,rht,RR(ind));
}
}
void updata(int st,int ed,int lft,int rht,int ind)
{
if(st<=lft&&rht<=ed) cnt[ind]++;
else
{
PushDown(ind);
int mid=MID(lft,rht);
if(st<=mid) updata(st,ed,lft,mid,LL(ind));
if(ed> mid) updata(st,ed,mid+1,rht,RR(ind));

}
}
int query(int pos,int lft,int rht,int ind)
{
if(lft==rht) return cnt[ind];
else
{
PushDown(ind);
int mid=MID(lft,rht);
if(pos<=mid) return query(pos,lft,mid,LL(ind));
else return query(pos,mid+1,rht,RR(ind));
}
}
}seg;

struct OP
{
int st,ed,id;
OP(){}
OP(int st,int ed,int id) : st(st),ed(ed),id(id) {}
bool operator<(const OP &B)const
{
return ed<B.ed;
}
}op[N];

int pos[N],res[N],a[N];

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(pos,-1,sizeof(pos));

int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
pos[a[i]]=i;
}
for(int i=0;i<m;i++)
{
int st,ed; scanf("%d%d",&st,&ed);
op[i]=OP(st,ed,i);
}

seg.build(1,n,1);

sort(op,op+m);

int ind=0;
for(int i=1;i<=n;i++)
{
int tmp=a[i];
if(pos[tmp-1]>=1&&pos[tmp-1]<=i)
{
//cout<<"updata="<<1<<" "<<pos[tmp-1]<<endl;
seg.updata(1,pos[tmp-1],1,n,1);
}
if(pos[tmp+1]>=1&&pos[tmp+1]<=i)
{
//cout<<"updata="<<1<<" "<<pos[tmp+1]<<endl;
seg.updata(1,pos[tmp+1],1,n,1);
}

while(ind<m&&op[ind].ed==i)
{
int tmp=op[ind].ed-op[ind].st+1;
//cout<<"query="<<op[ind].st<<" "<<op[ind].ed<<" "<<seg.query(op[ind].st,1,n,1)<<endl;
res[op[ind].id]=tmp-seg.query(op[ind].st,1,n,1);
ind++;
}
}
for(int i=0;i<m;i++) printf("%d\n",res[i]);
}
return 0;
}

1. 05年父亲单位调动，从中原油田调到胜利油田，当时我小学5年级，转学的那一段时间历历在目，转眼已经要研究生了，哎时间啊

2. 05年父亲单位调动，从中原油田调到胜利油田，当时我小学5年级，转学的那一段时间历历在目，转眼已经要研究生了，哎时间啊

3. 05年父亲单位调动，从中原油田调到胜利油田，当时我小学5年级，转学的那一段时间历历在目，转眼已经要研究生了，哎时间啊

4. 05年父亲单位调动，从中原油田调到胜利油田，当时我小学5年级，转学的那一段时间历历在目，转眼已经要研究生了，哎时间啊

5. 05年父亲单位调动，从中原油田调到胜利油田，当时我小学5年级，转学的那一段时间历历在目，转眼已经要研究生了，哎时间啊

6. 05年父亲单位调动，从中原油田调到胜利油田，当时我小学5年级，转学的那一段时间历历在目，转眼已经要研究生了，哎时间啊

7. 05年父亲单位调动，从中原油田调到胜利油田，当时我小学5年级，转学的那一段时间历历在目，转眼已经要研究生了，哎时间啊

8. 05年父亲单位调动，从中原油田调到胜利油田，当时我小学5年级，转学的那一段时间历历在目，转眼已经要研究生了，哎时间啊

9. 05年父亲单位调动，从中原油田调到胜利油田，当时我小学5年级，转学的那一段时间历历在目，转眼已经要研究生了，哎时间啊

10. 05年父亲单位调动，从中原油田调到胜利油田，当时我小学5年级，转学的那一段时间历历在目，转眼已经要研究生了，哎时间啊