線分樹模版兵士が敵を殺す
2304 ワード
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
typedef struct SegTree
{
int left,right;
int amountmax,amountmin;
struct SegTree *Lchild, *Rchild;
}SegTreeNode;
int minp,maxp;
SegTree* BuildSegTree(int L,int R)
{
SegTree *node;
node=(SegTree *)malloc(sizeof(SegTreeNode));
node->left=L;
node->right=R;
node->amountmax=-1;
node->amountmin=100000010;
int M=(L+R)/2;
if(L==R) node->Rchild=node->Lchild=NULL;
else if(L+1==R)
{
node->Lchild=BuildSegTree(L,L);
node->Rchild=BuildSegTree(R,R);
}
else
{
node->Lchild=BuildSegTree(L,M);
node->Rchild=BuildSegTree(M+1,R);
}
return node;
}
void InitSegTree(SegTree *root,int initnum,int initamount)
{
int L=root->left,R=root->right;
if(L<=initnum&&initnum<=R)
{
if(root->amountmax<initamount) root->amountmax=initamount;
if(root->amountmin>initamount) root->amountmin=initamount;
if(L==R) return ;
int M=(R+L)/2;
if(initnum<=M) InitSegTree(root->Lchild,initnum,initamount);
else InitSegTree(root->Rchild,initnum,initamount);
}
}
void findm(SegTree *root, int a,int b)
{
int L=root->left,R=root->right;
if(a==L&&b==R)
{
if(maxp<root->amountmax) maxp=root->amountmax;
if(minp>root->amountmin) minp=root->amountmin;
return ;
}
int M=(L+R)/2;
if(b<=M) findm(root->Lchild,a,b);
if(M<a) findm(root->Rchild,a,b);
if(a<=M&&M<b)
{
findm(root->Lchild,a,M);findm(root->Rchild,M+1,b);
}
}
int main()
{
int n,m,i,e;
scanf("%d%d",&n,&m);
SegTree *root;
root=BuildSegTree(1,n);
for(i=1;i<=n;i++)
{
scanf("%d",&e);
InitSegTree(root,i,e);
}
int a,b;
for(i=1;i<=m;i++)
{
minp=100000010;maxp=-1;
scanf("%d%d",&a,&b);
findm(root,a,b);
printf("%d
",maxp-minp);
}
return 0;
}