Group [HDU - 4638] [오프라인 트 리 배열]

4818 단어 데이터 구조오프라인 트 리 배열
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 개 수 를 먼저 제시 한 뒤 구간 내 연속 수의 개수 (하나 도 연속 되 지 않 으 면 자신 과 연속 되 더 라 도 한 조로 한다) 를 묻 는 것 이다.
  예 를 들 어 우 리 는 5 개의 숫자 가 있 는데 {3, 1, 2, 5, 4} 이다.조회 [2, 4] 의 연속 수의 개 수 는 바로 {1, 2}, {5} 이다. 문 제 는 우리 가 이 사상 을 어떻게 바 꿔 야 하 느 냐 하 는 것 이다.
  처음에 저 는 예전 에 구간 의 상호 질 수 를 구 하 는 개수 라 고 생각 했 습 니 다. 그 때 는 일정한 순서에 따라 순 서 를 매 긴 다음 에 질 인자 의 다음 사람 이 나타 나 는 위 치 를 미리 처리 하고 업 데 이 트 를 했 습 니 다. 그런데 이 문 제 는 실 용적 이지 않 았 습 니 다. 이 수 를 넣 으 면 '4' 이 고 '3', '5' 를 만나면 처리 해 야 하지만 '3', '5' 의 위치 에 있 으 면 '2', '6' 을 만 들 수 있 습 니 다.잠깐 만.
  그리고 방법 을 생각해 보 세 요. 만약 그의 좌우 가 조회 구간 안에 나타 나 면 전달 하고 옮 길 수 있 지 않 을까요?조회 의 왼쪽 구간 상승 순 서 를 살 펴 보 세 요. 만약 에 전달 하 는 수량 이 그의 좌우 요소 값 이 나 타 났 다 면 해당 위치 에 + 1 을 붙 이 고 이렇게 끊임없이 판단 을 연속 합 니 다. 그러면 오른쪽 단점 의 불안정 성 은 처리 하기 어렵 습 니 다. 하지만 이렇게 전달 할 수도 있 습 니 다. 이런 전달 은 매번 조회 의 단점 에 가 야 하 는 오른쪽 구간 의 업 데 이 트 를 만족 시 켜 야 합 니 다.하지만 그동안 의 연속 관계 가 끊 어 지면 처리 하기 가 쉽 지 않 을 텐 데................................................ 
  그래서 나 는 방법 을 바 꾸 어 왼쪽 구간 의 순 서 를 내 렸 다. 이렇게 하면 나타 난 노드 에 '+ 1' 을 붙 여 그들 사이 의 관계 가 존재 한 다 는 것 을 표시 할 수 있다. 만약 좌우 구간 이 모두 존재 한다 면 모두 + 1 한 다음 에 조회 한 각 구간 은 구간 의 길이 로 관 계 를 직접 빼 면 된다.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define ls rt<<1
#define rs rt<<1|1
#define Lson ls, l, mid
#define Rson rs, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 1e5 + 7;
int N, M, a[maxN], val_pos[maxN];   //val_pos[]           ，       
struct ques
{
    int l, r, id;
    ques(int a=0, int b=0, int c=0):l(a), r(b), id(c) {}
}q[maxN];
int ans[maxN];  //  
bool cmp(ques e1, ques e2) { return e1.l > e2.l; } //          ……   
int trie[maxN];
inline void update(int i, int val)
{
    if(i == 0) return;
    while(i < maxN)
    {
        trie[i] += val;
        i += lowbit(i);
    }
}
inline int query(int i)
{
    int ans = 0;
    while(i)
    {
        ans += trie[i];
        i -= lowbit(i);
    }
    return ans;
}
int main()
{
    int T;  scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &N, &M);
        memset(trie, 0, sizeof(trie));
        for(int i=1; i<=N; i++)
        {
            scanf("%d", &a[i]);
            val_pos[a[i]] = i;
        }
        for(int i=1; i<=M; i++)
        {
            scanf("%d%d", &q[i].l, &q[i].r);
            q[i].id = i;
        }
        sort(q+1, q+M+1, cmp);  //  v  ，        
        int j = N;
        for(int i=1; i<=M; i++)
        {
            while(j >= q[i].l)
            {
                if(a[j] < N)
                {
                    if(val_pos[a[j] + 1] >= j)
                    {
                        update(val_pos[a[j] + 1], 1);
                    }
                }
                if(a[j] > 1)
                {
                    if(val_pos[a[j] - 1] >= j)
                    {
                        update(val_pos[a[j] - 1], 1);
                    }
                }
                j--;
            }
            ans[q[i].id] = (q[i].r - q[i].l + 1) - ( query(q[i].r) - query(q[i].l - 1) );
        }
        for(int i=1; i<=M; i++) printf("%d
", ans[i]);
    }
    return 0;
}

TypeScript 함수 소개 — 객체가 삭제되고 다시 로드됩니다.
선형 구조 4 Pop Sequence (25 분)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage