竞赛讨论区 > H题用线段树找最大最小值都为x超内存
头像
血腥刽子手
发布于 2019-06-15 12:08
+ 关注

H题用线段树找最大最小值都为x超内存

线段树找最大最小值都是x,为啥说我超内存了鸭?是递归层数太多了嘛?可是别人***树都行诶
#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) (m>n?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=20180623;
int Min[maxn<<2],Max[maxn<<2];
void pushup(int id)
{
    Max[id]=max(Max[id<<1],Max[id<<1|1]);
    Min[id]=min(Min[id<<1],Min[id<<1|1]);
}

void Build(int id,int L,int R)
{
    if(L==R)
    {
        scanf("%d",&Min[id]);
        Max[id]=Min[id];
        return ;
    }
    int mid=L+R>>1;
    Build(id<<1,L,mid);
    Build(id<<1|1,mid+1,R);
    pushup(id);
}
int query(int id,int L,int R,int qL,int qR,int x)
{
    if(qL<=L&&qR>=R&&Max[id]==x&&Min[id]==x)
    {
        return R-L+1;
    }
    int mid=L+R>>1;
    int res=0;
    if(L<=qL)res+=query(id<<1,L,mid,qL,qR,x);
    if(R>mid)res+=query(id<<1|1,mid+1,R,qL,qR,x);
    return res;
}
int main()
{
    int N,Q;
    while(cin>>N>>Q)
    {
        Build(1,1,N);
        while(Q--)
        {
            int L1,R1,L2,R2,x;
            scanf("%d%d%d%d%d",&L1,&R1,&L2,&R2,&x);
            LL res1=query(1,1,N,L1,R1,x);
            LL res2=query(1,1,N,L2,R2,x);
            cout<<res1%MOD<<endl<<res2%MOD<<endl<<res1*res2%MOD<<endl;
        }
    }
}

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐