两道离线线段树。

比赛时候没想到。。。。

扫描数组，i从1到n，线段树维护从1到i每一个约数（1~50000）的出现的最近位置，线段树存储的是约数的最大值

#include
#include
#include
#include

using namespace std;

const int N=50050;

struct Interval{
    int l,r,id;
}in[N];

struct Tree{
    int l,r,Max;
}tree[N<<2];

int n,m;
int a[N];
int pre[N];
int ans[N];
vector factor[N];


void init(){
    for(int i=1;i>1;
        build(l,mid,id<<1);
        build(mid+1,r,id<<1|1);
    }
}

void update(int pos,int val,int id){
    tree[id].Max=max(tree[id].Max,val);
    if(tree[id].l==tree[id].r) return ;
    int mid=(tree[id].l+tree[id].r)>>1;
    if(mid>=pos) update(pos,val,id<<1);
    else update(pos,val,id<<1|1);
}

int query(int l,int r,int id){
    if(tree[id].l==l && tree[id].r==r) return tree[id].Max;
    int mid=(tree[id].l+tree[id].r)>>1;
    if(mid>=r) return query(l,r,id<<1);
    else if(mid 
 
 
 
 

 BOJ的那题找不到了，做完这道题之后，发现这两题很像，都是离线线段树做法。（这道题还是队友出的，膜拜）
 
 
 
 
 

 先为数组中每个点i一个最小区间l,r满足a[i]>a[l] && a[i] 
 
然后i从1开始扫描，每次把能加入的点加入，然后处理右端点为i的查询
 
 
 
 
 
#include
#include
#include
#include
using namespace std;
const int MAXN = 100000+5;
const int INF = 0x3f3f3f3f;
int T, N, Q, a[MAXN], s[MAXN], t[MAXN];
int idq[MAXN], q[MAXN], cnt[MAXN], p[MAXN];
int x[MAXN], y[MAXN], ida[MAXN];
int Tr[MAXN<<2], mark[MAXN<<2];
void Build(int idx, int L, int R)
{
	Tr[idx] = mark[idx] = 0;
	if (L == R)
		return;
	int left = idx<<1, right = idx<<1|1, mid = (L+R)>>1;
	Build(left, L, mid);
	Build(right, mid+1, R);
}
void PushDown(int idx)
{
	int left = idx<<1, right = idx<<1|1, &mk = mark[idx];
	Tr[left] += mk;
	mark[left] += mk;
	Tr[right] += mk;
	mark[right] += mk;
	mk = 0;
}
void Update(int idx, int L, int R, int l, int r, int c)
{
	if (l <= L && R <= r)
	{
		Tr[idx] += c;
		mark[idx] += c;
		return;
	}
	if (mark[idx])
		PushDown(idx);
	int left = idx<<1, right = idx<<1|1, mid = (L+R)>>1;
	if (l <= mid)
		Update(left, L, mid, l, r, c);
	if (mid < r)
		Update(right, mid+1, R, l, r, c);
}
int Query(int idx, int L, int R, int x)
{
	if (x == L && R == x)
		return Tr[idx];
	if (mark[idx])
		PushDown(idx);
	int left = idx<<1, right = idx<<1|1, mid = (L+R)>>1;
	if (x <= mid)
		return Query(left, L, mid, x);
	else
		return Query(right, mid+1, R, x);
}
bool cmpq(const int &a, const int &b)
{
	return t[a] < t[b];
}
bool cmpa(const int &a, const int &b)
{
	return y[a] < y[b];
}
int main()
{
	//freopen("data.in", "r", stdin);
	//freopen("data.out", "w", stdout);
	scanf("%d", &T);
	for (int cas = 1; cas <= T; cas++)
	{
		printf("Case %d:\n", cas);
		scanf("%d", &N);
		stack stal, star;
		a[0] = 0;
		stal.push(0);
		for (int i = 1; i <= N; i++)
		{
			scanf("%d", &a[i]);
			while (a[i] <= a[stal.top()])
				stal.pop();
			x[i] = stal.top();
			stal.push(i);
		}
		a[N+1] = INF;
		star.push(N+1);
		for (int i = N; i >= 1; i--)
		{
			while (a[i] >= a[star.top()])
				star.pop();
			y[i] = star.top();
			star.push(i);
			ida[i] = i;
		}
		sort(ida+1, ida+1+N, cmpa);
		scanf("%d", &Q);
		for (int i = 1; i <= Q; i++)
		{
			scanf("%d%d", &s[i], &t[i]);
			if (s[i] > t[i])
				swap(s[i], t[i]);
			idq[i] = i;
			q[i] = 0;
		}
		sort(idq+1, idq+1+Q, cmpq);
		Build(1, 1, N);
		for (int i = 1, j = 1, k = 1; i <= N; i++)
		{
			for (; y[ida[k]] == i && k <= N; k++) if (x[ida[k]])
				Update(1, 1, N, 1, x[ida[k]], 1);
			for (; t[idq[j]] == i && j <= Q; j++)
				q[idq[j]] = Query(1, 1, N, s[idq[j]]);
		}
		for (int i = 1; i <= Q; i++)
			printf("%d\n", q[i]);
	}
	return 0;
}