HDU4638:Group(线段树离线处理)

Problem Description

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

题意:给出一个数组。每次查询l,r。看区间内能分成几个连续的数列

思路:离线处理全部查询
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
using namespace std;

#define ls 2*i
#define rs 2*i+1
#define UP(i,x,y) for(i=x;i<=y;i++)
#define DOWN(i,x,y) for(i=x;i>=y;i--)
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define LL long long
#define N 100005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define EXP 1e-8
#define rank rank1
const int mod = 10007;

struct node
{
    int l,r,val;
} a[N*4],s[N];

int num[N],pos[N],vis[N],ans[N];
int n,m;

int cmp(node a,node b)
{
    return a.r<b.r;
}

void build(int l,int r,int i)
{
    a[i].l = l;
    a[i].r = r;
    a[i].val = 0;
    if(l==r) return;
    int mid = (l+r)/2;
    build(l,mid,ls);
    build(mid+1,r,rs);
}

void updata(int i,int pos,int v)
{
    a[i].val+=v;
    if(a[i].l==a[i].r) return;
    int mid = (a[i].l+a[i].r)/2;
    if(pos<=mid) updata(ls,pos,v);
    else updata(rs,pos,v);
}

int query(int l,int r,int i)
{
    if(a[i].l==l&&a[i].r==r)
    {
        return a[i].val;
    }
    int mid = (a[i].l+a[i].r)/2;
    if(r<=mid) return query(l,r,ls);
    if(l>mid) return query(l,r,rs);
    return query(l,mid,ls)+query(mid+1,r,rs);
}

int main()
{
    int t,i,j,k,cnt;
    scanf("%d",&t);
    while(t--)
    {
        MEM(vis,0);
        scanf("%d%d",&n,&m);
        for(i = 1; i<=n; i++)
        {
            scanf("%d",&num[i]);
            pos[num[i]] = i;
        }
        for(i = 1; i<=m; i++)
        {
            scanf("%d%d",&s[i].l,&s[i].r);
            s[i].val = i;
        }
        sort(s+1,s+1+m,cmp);
        build(1,n,1);
        cnt = 1;
        for(i = 1; i<=n&&cnt<=m; i++)
        {
            updata(1,i,1);
            vis[num[i]]=1;
            if(vis[num[i]-1]) updata(1,pos[num[i]-1],-1);
            if(vis[num[i]+1]) updata(1,pos[num[i]+1],-1);
            while(s[cnt].r==i&&cnt<=m)
            {
                ans[s[cnt].val] = query(s[cnt].l,s[cnt].r,1);
                cnt++;
            }
        }
        for(i = 1; i<=m; i++)
            printf("%d\n",ans[i]);
    }

    return 0;
}
时间: 06-30

HDU4638:Group(线段树离线处理)的相关文章

Super Mario(线段树离线区间k值)

以前见过这题,没做出来,知道是离线处理,这次仔细想了下, 首先把出现的高度都map离散化一下,以离散化出来的数目g建树,把每个位置都开俩个vector,一个存以这个位置为L的询问,一个存以这个位置为R的询问. 然后从1-g 进行更新,假如当前i是以第j个区间的开始位置,那么这时就可以询问一下<=p[j].h的个数s,显然这时第J个区间多加的,需要减掉,p[j].sum-=s; 然后更新第i个数,update(a[i],1,g,1);再找到某第k区间是以i结尾的,那么依旧询问一下,得出s,p[k]

线段树+离线 hdu5654 xiaoxin and his watermelon candy

传送门:点击打开链接 题意:一个三元组假设满足j=i+1,k=j+1,ai<=aj<=ak,那么就好的.如今告诉你序列.然后Q次询问.每次询问一个区间[l,r],问区间里有多少个三元组满足要求 思路:刚開始看错题目了,原来三元组是连续3个,这作为bc最后一题也太水了把. . . 先一遍预处理.把连续3个满足条件的找出来,放到还有一个数组里排序去重,用这个数组来给三元组哈希.再扫一遍给三元组在之前那个排序好的数组里二分一下得到下标,大概就是哈希一下,用一个数字来表示. 之后的查询.事实上就是.在

gcd(线段树离线处理)——HDU 4630

对应HDU题目:点击打开链接 No Pain No Game Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 1801    Accepted Submission(s): 770 Problem Description Life is a game,and you lose it,so you suicide. But you can

SPOJ--K-query (线段树离线) 离线操作解决一下问题

K-query Given a sequence of n numbers a1, a2, ..., an and a number of k- queries. A k-query is a triple (i, j, k) (1 ≤ i ≤ j ≤ n). For each k-query (i, j, k), you have to return the number of elements greater than k in the subsequence ai, ai+1, ...,

51nod 1463 找朋友(线段树+离线处理)

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1463 题意: 思路: 好题! 先对所有查询进行离线处理,按照右区间排序,因为k一共最多只有10个,所有在该区间内的B数组,每次枚举K值,通过这样的方式来得到另外一个B值.但是这样得到的B值它在B数组中的位置必须在当前数的左边.如下图:(j为当前数在B数组中的位置,pos为计算得到的另一个B值在数组中的位置) 这两个数的和记录在pos中,这里pos的位置必须在j的左边,假

玲珑oj 1117 线段树+离线+离散化,laz大法

1117 - RE:从零开始的异世界生活 Time Limit:1s Memory Limit:256MByte Submissions:438Solved:68 DESCRIPTION 486到了异世界,看到了一群可爱的妹子比如蕾姆啊,艾米莉亚啊,拉姆啊,白鲸啊,怠惰啊等等!有一天膜女告诉486说她的能力可能不能再用了,因为膜女在思考一个数据结构题,没心情管486了.486说我来帮你做,膜女说你很棒棒哦! 给一个集合,最开始为空(不是数学上的集合)五个操作: 1.插入x2.把小于x的数变成x3

HDU3874 线段树 + 离线处理

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3874 , 线段树(或树状数组) + 离线处理 下午做了第一道离线处理的题目(HDU4417),多少有点感觉,顺便就把这道题也给做了. 这道题就是要求某个区间内不重复数的和,自己在网上百度后参考别人的方法才AC的.参考来源:http://www.cnblogs.com/gj-Acit/p/3249827.html 这道题还是需要先离线处理数据,具体方法: ① 先用线段树把树给建立起来: ② 先把所有要

HDU4417 线段树 + 离线处理

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4417 , 线段树(或树状数组) + 离线处理 最近看了几道线段树的题都是需要离线处理数据的,正好这块比较手生,就练练了.  这道题主要的地方就是离线处理数据,具体想法: ① 先把所有位置的高度都存下来,然后排序,注意保存下标: ② 把所有询问存下来,然后按照询问的高度进行排序,同注意保存下标: ③ 对于排序后的每次询问的处理:由于每个位置的高度都已经存了下来并且进行了排序,所以可以按照顺序将每个点插

HDU4638——Group(树状数组+离线操作)

题目链接 题目大意 n个数的序列,m次询问. 求一段区间连续数字的段数 . (1 3 5 4 2) 询问[2,4]区间则3,5,4为连续序列输出 1 . 解题思路 我觉得这是一道不错的题目. 定义线段是求的连续序列. 首先将所有的询问离线,按照Li递增排序. 我们可以用一个结构维护Li为起点加入所有点后的各区间线段数,对于每个以Li为起点的询问进行处理. 当然这样不够,我们还要消除Li之前加入的点的影响. 所以我们可以用树状数组或者线段树维护区间的线段数. 利用树状数组维护:树状数组在对于线段的