线段树找最大最小值都是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;
}
}
}
#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) 回帖