65pts,线段树写法,奇怪的错误信息
查看原帖
65pts,线段树写法,奇怪的错误信息
416242
New_hope楼主2023/8/15 14:48
read 0, expected -

是什么地方出问题了

#include<bits/stdc++.h>
#define LL long long
#define Maxn (int)1e5 + 4
#define inf (int)2e9
#define L fa << 1
#define R fa << 1 | 1
#define mid (l+r >> 1)
using namespace std;

struct segt {
   bool neg,posi,zero;
   LL maxn,minn,maxneg,minnposi;
};
segt a[Maxn << 2],b[Maxn << 2];

LL A[Maxn],B[Maxn];

void push_up_a(LL fa) {
   a[fa].neg = a[L].neg | a[R].neg;
   a[fa].posi = a[L].posi | a[R].posi;
   a[fa].zero = a[L].zero | a[R].zero;
   a[fa].maxn = max(a[L].maxn, a[R].maxn);
   a[fa].minn = min(a[L].minn, a[R].minn);
   a[fa].maxneg = max(a[L].maxneg, a[R].maxneg);
   a[fa].minnposi = min(a[L].minnposi, a[R].minnposi);
   return ;
}
void push_up_b(LL fa) {
   b[fa].neg = b[L].neg | b[R].neg;
   b[fa].posi = b[L].posi | b[R].posi;
   b[fa].zero = b[L].zero | b[R].zero;
   b[fa].maxn = max(b[L].maxn, b[R].maxn);
   b[fa].minn = min(b[L].minn, b[R].minn);
   b[fa].maxneg = max(b[L].maxneg, b[R].maxneg);
   b[fa].minnposi = min(b[L].minnposi, b[R].minnposi);
   return ;
}
void build_a(LL fa,LL l,LL r) {
   a[fa].maxneg = -inf, a[fa].minnposi = inf;
   if(l == r) {
      if(A[l] < 0) {
         a[fa].neg = 1;
         a[fa].maxneg = A[l];
      }
      if(A[l] == 0) a[fa].zero = 1;
      if(A[l] > 0) {
         a[fa].posi = 1;
         a[fa].minnposi = A[l];
      }
      a[fa].maxn = a[fa].minn = A[l];
      return ;
   }
   build_a(L,l,mid), build_a(R,mid+1,r); push_up_a(fa);
}
void build_b(LL fa,LL l,LL r) {
   b[fa].maxneg = -inf, b[fa].minnposi = inf;
   if(l == r) {
      if(B[l] < 0) {
         b[fa].neg = 1;
         b[fa].maxneg = B[l];
      }
      if(B[l] == 0) b[fa].zero = 1;
      if(B[l] > 0) {
         b[fa].posi = 1;
         b[fa].minnposi = B[l];
      }
      b[fa].maxn = b[fa].minn = B[l];
      return ;
   }
   build_b(L,l,mid), build_b(R,mid+1,r); push_up_b(fa);
}
segt query_a(LL fa,LL l,LL r,LL ql,LL qr) {
   if(ql <= l && r <= qr) return a[fa];

   if(qr <= mid) return query_a(L,l,mid,ql,qr);
   else if(ql > mid) return query_a(R,mid+1,r,ql,qr);
   else {
      segt ls = query_a(L,l,mid,ql,qr);
      segt rs = query_a(R,mid+1,r,ql,qr);
      segt res;
      res.neg = ls.neg | rs.neg, res.posi = ls.posi | rs.posi, res.zero = ls.zero | rs.zero;
      res.maxn = max(ls.maxn, rs.maxn), res.minn = min(ls.minn, rs.minn);
      res.maxneg = max(ls.maxneg, rs.maxneg), res.minnposi = min(ls.minnposi, rs.minnposi);
      return res;
   }
}
segt query_b(LL fa,LL l,LL r,LL ql,LL qr) {
   if(ql <= l && r <= qr) return b[fa];

   if(qr <= mid) return query_b(L,l,mid,ql,qr);
   else if(ql > mid) return query_b(R,mid+1,r,ql,qr);
   else {
      segt ls = query_b(L,l,mid,ql,qr);
      segt rs = query_b(R,mid+1,r,ql,qr);
      segt res;
      res.neg = ls.neg | rs.neg, res.posi = ls.posi | rs.posi, res.zero = ls.zero | rs.zero;
      res.maxn = max(ls.maxn, rs.maxn), res.minn = min(ls.minn, rs.minn);
      res.maxneg = max(ls.maxneg, rs.maxneg), res.minnposi = min(ls.minnposi, rs.minnposi);
      return res;
   }
}

LL judge(segt a,segt b) {
   
   LL res;
   if(a.posi && !(a.neg | a.zero)) {
      if(b.neg) res = a.minn * b.minn;
      else res = a.maxn * b.minn;
   }
   else if(a.neg && !(a.posi | a.zero)) {
      if(b.posi) res = a.maxn * b.maxn;
      else res = a.minn * b.maxn;
   }
   else if(a.zero && !(a.posi | a.neg)) {
      res = 0;
   }
   else if(a.posi && a.zero && !a.neg) {
      if(b.posi && !(b.neg | b.zero)) res = a.maxn * b.minn;
      else res = 0;
   }
   else if(a.neg && a.posi && !a.zero) {
      if(b.posi && !(b.neg | b.zero)) res = a.maxn * b.minn;
      else if(!b.zero) {
         if(b.posi) {
            res = max(a.minnposi*b.minn, a.maxneg*b.maxn);
         }
         else res = a.minn*b.maxn;
      }
      else res = 0;
   }
   else if(a.neg && a.zero && !a.posi) {
      if(b.neg && !(b.posi | b.zero)) res = a.minn*b.maxn;
      else res = 0;
   }
   else if(a.neg && a.zero && a.posi){
      if(b.posi && !(b.neg | b.zero)) {
         res = a.maxn*b.minn;
      }
      else if(b.neg && !(b.posi | b.zero)) {
         res = a.minn*b.maxn;
      }
      else res = 0;
   }
   return res;
}
int main() {

   LL n,m,q;
   scanf("%lld %lld %lld",&n,&m,&q);
   for(LL i = 1; i <= n; i ++) scanf("%lld",&A[i]);
   for(LL i = 1; i <= m; i ++) scanf("%lld",&B[i]);
   build_a(1,1,n), build_b(1,1,m);
   
   for(LL i = 1; i <= q; i ++) {
      LL l1,r1,l2,r2;
      scanf("%lld %lld %lld %lld",&l1,&r1,&l2,&r2);
      segt a = query_a(1,1,n,l1,r1);
      segt b = query_b(1,1,m,l2,r2);
      LL ans = judge(a,b);
      printf("%lld\n",ans);
   }
   return 0;
}
2023/8/15 14:48
加载中...