2016 大连网络赛 & hdu5875 (优先队列+离线）★

2019-04-14 18:48发布

站内文章 / 模拟电子
14598 0 1198
题意：给你一个区间，求a_l%a_(l+1)%a_(l+2)%…%a_r 的值 分析：因为一个数连续模一个比他模数小的数不会模超过30次，所以预处理记录下每个位置的30次变化，离线输出就可。 具体做法就是优先队列保存一个结构体，里面记录模数以及原始位置，On扫一遍，对于每个位置，队首元素模数大于该位置数时，一直弹出，并压入更新后的模数及位置，同时记录下相关信息。 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define L(i) i<<1 #define R(i) i<<1|1 #define INF 0x3f3f3f3f #define pi acos(-1.0) #define eps 1e-3 #define maxn 300100 #define MOD 1000000007 struct node { int x,pos; bool operator < (const node & a)const { return x < a.x; } }st,ans[maxn][35]; int n; int a[maxn]; int num[maxn]; int main() { int t,C = 1; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); ans[i][0].pos = i; ans[i][0].x = a[i]; num[i] = 1; } priority_queue q; for(int i = 1; i <= n; i++) { while(!q.empty() && a[i] <= q.top().x) { st = q.top(); q.pop(); int k = st.x % a[i]; //printf("%d %d %d %d ",i,st.x,st.pos,k); ans[st.pos][num[st.pos]].x = k; ans[st.pos][num[st.pos]].pos = i; num[st.pos]++; st.x = k; q.push(st); } st.x = a[i]; st.pos = i; q.push(st); } int m; scanf("%d",&m); while(m--) { int x,y; scanf("%d%d",&x,&y); int flag = 0; for(int i = 0; i < num[x]; i++) { if(ans[x][i].pos > y) { printf("%d ",ans[x][i-1].x); flag = 1; break; } } //printf("%d ",flag); if(!flag) printf("%d ",ans[x][num[x]-1].x); } } return 0; }

热门文章