HDU 5875 Function 大连网络赛 线段树
Function
Time Limit: 7000/3500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1498 Accepted Submission(s): 553
Problem Description
The shorter, the simpler. With this problem, you should be convinced of this truth. You are given an array of postive integers, and queries in the form . A function is defined as: You job is to calculate , for each query .
Input
There are multiple test cases. The first line of input contains a integer , indicating number of test cases, and test cases follow. For each test case, the first line contains an integer . The second line contains space-separated positive integers: . The third line contains an integer denoting the number of queries. The following lines each contain two integers , representing a query.
Output
For each query, output on one line.
Sample Input
1
3
2 3 3
1
1 3Sample Output
2
函数的意思解读出来就是在l到r的区间里，a[l],对区间里的数，逐个取余那么比a[l]大的数，取余不变，主要看比a[l]小的数，所以在区间里找第一个比a[l]小的数，然后继续在剩下的区间里面找比取完余的a[l]小的数#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string>
#include <stdlib.h>
#include <vector>
using namespace std;
const int maxn=1e5;
int cmin[maxn*4+5];
int a[maxn+5];
int n,m;
int l,r;
int x;
void PushUp(int node)
{
cmin[node]=min(cmin[node<<1],cmin[node<<1|1]);
}
void build(int node,int begin,int end)
{
if(begin==end)
{
scanf("%d",&x);
cmin[node]=x;
a[begin]=x;
return;
}
int m=(begin+end)>>1;
build(node<<1,begin,m);
build(node<<1|1,m+1,end);
PushUp(node);
}
bool tag;
int minn;
int pos;
void query(int node,int begin,int end,int left,int right,int value)
{
if(value<cmin[node])
return;
if(begin==end)
{
minn=cmin[node];
pos=begin;
tag=true;
return;
}
int m=(begin+end)>>1;
if(left<=m)
query(node<<1,begin,m,left,right,value);
if(tag) return;
if(right>m)
query(node<<1|1,m+1,end,left,right,value);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
build(1,1,n);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&l,&r);
tag=false;
int x=a[l];
if(l==r)
{
printf("%d\n",x);
continue;
}
query(1,1,n,l+1,r,x);
if(!tag)
printf("%d\n",x);
else
{
while(1)
{
tag=false;
x%=minn;
if(pos+1>r)
{
printf("%d\n",x);
break;
}
query(1,1,n,pos+1,r,x);
if(!tag)
{
printf("%d\n",x);
break;
}
}
}
}
}
return 0;
}