程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4630 No Pain No Game(線段樹離線處理)

HDU 4630 No Pain No Game(線段樹離線處理)

編輯:C++入門知識

HDU 4630 No Pain No Game(線段樹離線處理)


題意:給你一個n的全排列, q個操作, 每個操作是一個區間,要求求出這個區間中任意兩個數的gcd的最大值。

思路:一個數是兩個數的公約數, 等價於一個數可以被兩個整數同時整除。 所以我們可以算出每一個數的所有約數, 然後求一個區間中被超過兩個數整除的數中的最大值即可。

維護區間最大值, 我們可以用線段樹來維護。 因為我們難以同時維護一個區間, 所以我們離線處理, 按照r排序, 那麼每次如果當前數的一個約數曾經出現過, 就在之前出現的點加入線段樹, 每次順便查詢即可。

細節參見代碼:

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 50000 + 10;
int T,n,m,maxv[maxn<<2],a[maxn],pre[maxn],ans[maxn];
struct node {
    int id, l, r;
    node(int id=0, int l=0, int r=0):id(id), l(l), r(r) {}
    bool operator < (const node& rhs) const {
        return r < rhs.r;
    }
}op[maxn];
void pushup(int o) {
    maxv[o] = max(maxv[o<<1], maxv[o<<1|1]);
}
void build(int l, int r, int o) {
    int m = (l + r) >> 1;
    maxv[o] = 0;
    if(l == r) return ;
    build(l, m, o<<1);
    build(m+1, r, o<<1|1);
}
void update(int L, int R, int v, int l, int r, int o) {
    int m = (l + r) >> 1;
    if(L <= l && r <= R) {
        maxv[o] = max(maxv[o], v);
        return ;
    }
    if(L <= m) update(L, R, v, l, m, o<<1);
    if(m < R) update(L, R, v, m+1, r, o<<1|1);
    pushup(o);
}
int query(int L, int R, int l, int r, int o) {
    int m = (l + r) >> 1;
    if(L <= l && r <= R) {
        return maxv[o];
    }
    int ans = 0;
    if(L <= m) ans = max(ans, query(L, R, l, m, o<<1));
    if(m < R) ans = max(ans, query(L, R, m+1, r, o<<1|1));
    pushup(o);
    return ans;
}
int q, r, l;
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
        }
        scanf("%d",&q);
        for(int i=0;i

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved