首页 > 代码库 > HDU 5042 GCD pair 预处理+二分 分段
HDU 5042 GCD pair 预处理+二分 分段
点击打开链接
#include <stdio.h> #include <string.h> #include <iostream> #include <cmath> #include <algorithm> #include <vector> using namespace std; typedef long long ll; ll gcd(ll x, ll y){ if(x>y)swap(x,y); while(x){ y%=x; swap(x,y); } return y; } const ll inf = 1<<30; const double eps = 1e-8; typedef pair<ll,ll> pii; template <class T> inline bool rd(T &ret) { char c; ll sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } #define N 100005 struct node{ ll pos, l, r, gval; node(ll a=0,ll b=0,ll c=0,ll d=0):pos(a),l(b),r(c),gval(d){} bool operator < (const node &x) const { if(x.gval != gval) return gval < x.gval; if(x.pos != pos) return pos < x.pos; return r < x.r; } }p[N*15]; vector<node> G[N]; ll a[N], n, que, top; pii ans; ll sum[N*15]; ll cnt[N*15]; void precal(){ G[n].push_back(node(n,n,n,a[n])); for(ll i = n-1; i; i--){ G[i].push_back(node(i,i,i,a[i])); for(ll j = 0; j < G[i+1].size(); j++){ node tmp = G[i+1][j]; ll x = gcd(a[i], tmp.gval); if(x == G[i][G[i].size()-1].gval) G[i][G[i].size()-1].r = tmp.r; else G[i].push_back(node(i, tmp.l, tmp.r, x)); } } top = 0; for(ll i = 1 ; i <= n; i++) for(ll j = 0; j < (ll)G[i].size(); j++) p[++top] = G[i][j]; sort(p+1, p+top+1); sum[0] = 0; for(ll i = 1; i <= top; i++) sum[i] = sum[i-1] + (ll)p[i].r-(ll)p[i].l+1LL; cnt[1] = 1; for(ll i = 2; i <= top; i++) cnt[i] = cnt[i-1] + (p[i-1].gval!=p[i].gval); } ll F(ll l, ll r){ ll z = 0, y = G[l].size()-1; // putchar('&');for(ll i =0;i<G[l].size(); i++)pt(G[l][i].gval),putchar(' ');puts(""); while(z < y) { ll mid = (z+y)>>1; // prllf("(%d,%d)\n", z, y); if(G[l][mid].r < r) z = mid+1; else y = mid; } return G[l][z].gval; } void Rank(ll l, ll r){ // puts("2--"); ll x = F(l,r); // puts("**"); node tmp = node(-inf, 0, 0, x); //1 ll now1 = lower_bound(p+1, p+1+top, tmp) - p; ans.first = (ll)cnt[now1]; tmp = node(l, l, r, x); ll now2 = lower_bound(p+now1, p+1+top, tmp) - p; ans.second = sum[now2-1] - sum[now1-1] + (ll)r - (ll)p[now2].l + 1LL; // puts("end2"); } void Select(ll k1, ll k2){ // puts("3--"); ans.first = -1; if(cnt[top] < k1)return ; ll L = lower_bound(cnt + 1,cnt + top + 1,k1) - cnt; ll R = upper_bound(cnt + 1,cnt + top + 1,k1) - cnt - 1; if(sum[R] - sum[L-1] < (ll)k2) return ; ll pos = lower_bound(sum+L, sum+R+1, (ll)k2 + sum[L-1]) - sum; ll tx = sum[pos] - sum[L-1] - (ll)k2; ans.first = (ll)p[pos].pos; ans.second = (ll)p[pos].r - tx; // puts("end3"); } void input(){ rd(n); rd(que); for(ll i = 1; i <= n; i++) { rd(a[i]); G[i].clear(); } G[0].clear(); } int main(){ char s[10]; ll T, Cas = 1, l, r; rd(T); while(T--){ input(); printf("Case #%I64d:\n", Cas++); precal(); while(que--){ scanf("%s", s); rd(l); rd(r); // prllf("(%d,%d)\n", l, r); if(s[0] == 'R') { Rank(l, r); pt(ans.first); putchar(' '); pt(ans.second); putchar('\n'); } else { Select(l, r); if(ans.first == -1)puts("-1"); else {pt(ans.first); putchar(' '); pt(ans.second); putchar('\n');} } } } return 0; } /* 1 3 6 6 2 4 RANK 1 1 SELECT 3 1 RANK 2 3 SELECT 2 2 SELECT 1 3 SELECT 1 4 */
HDU 5042 GCD pair 预处理+二分 分段
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。