S组T2为什么洛谷上A了,在infoj只有80???
  • 板块学术版
  • 楼主liuyufeng1
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/10/29 22:33
  • 上次更新2023/10/27 05:00:50
查看原帖
S组T2为什么洛谷上A了,在infoj只有80???
368515
liuyufeng1楼主2022/10/29 22:33

rt 代码如下:

#include<bits/stdc++.h>
using namespace std;

#define ll long long
// 这题要开long long!!!! 

const int maxn = 1e5 + 10;

struct node{
	ll l, r, znum, fnum, pnum, sz; // 正数个数 负数个数 0个数 
	ll zmax = 0, zmin = INT_MAX, fmax = INT_MIN, fmin = 0; //最大正数 最小正数 最大负数 最小负数 
}tree1[maxn*4], tree2[maxn*4];

ll n, m, q, a[maxn], b[maxn];
ll l1, r1, l2, r2;

void push_up1(ll x){
	tree1[x].znum = tree1[x*2].znum + tree1[x*2+1].znum;
	tree1[x].fnum = tree1[x*2].fnum + tree1[x*2+1].fnum;
	tree1[x].pnum = tree1[x*2].pnum + tree1[x*2+1].pnum;
	
	tree1[x].zmax = max(tree1[x*2].zmax, tree1[x*2+1].zmax);
	tree1[x].zmin = min(tree1[x*2].zmin, tree1[x*2+1].zmin);
	tree1[x].fmax = max(tree1[x*2].fmax, tree1[x*2+1].fmax);
	tree1[x].fmin = min(tree1[x*2].fmin, tree1[x*2+1].fmin);
}

void push_up2(ll x){
	tree2[x].znum = tree2[x*2].znum + tree2[x*2+1].znum;
	tree2[x].fnum = tree2[x*2].fnum + tree2[x*2+1].fnum;
	tree2[x].pnum = tree2[x*2].pnum + tree2[x*2+1].pnum;
	
	tree2[x].zmax = max(tree2[x*2].zmax, tree2[x*2+1].zmax);
	tree2[x].zmin = min(tree2[x*2].zmin, tree2[x*2+1].zmin);
	tree2[x].fmax = max(tree2[x*2].fmax, tree2[x*2+1].fmax);
	tree2[x].fmin = min(tree2[x*2].fmin, tree2[x*2+1].fmin);
}

void build1(ll i, ll l, ll r){
	tree1[i].l = l, tree1[i].r = r, tree1[i].sz = tree1[i].r - tree1[i].l + 1;
	if(l == r){
		if(a[l] > 0) tree1[i].znum++, tree1[i].zmax = tree1[i].zmin = a[l];
		else if(a[l] == 0) tree1[i].pnum++; 
		else tree1[i].fnum++, tree1[i].fmax = tree1[i].fmin = a[l];
		return;
	}
	ll mid = (l + r) >> 1;
	build1(i * 2, l, mid);
	build1(i * 2 + 1, mid + 1, r);
	push_up1(i);
}

void build2(ll i, ll l, ll r){
	tree2[i].l = l, tree2[i].r = r, tree2[i].sz = tree2[i].r - tree2[i].l + 1;
	if(l == r){
		if(b[l] > 0) tree2[i].znum++, tree2[i].zmax = tree2[i].zmin = b[l];
		else if(b[l] == 0) tree2[i].pnum++; 
		else tree2[i].fnum++, tree2[i].fmax = tree2[i].fmin = b[l];
		return;
	}
	ll mid = (l + r) >> 1;
	build2(i * 2, l, mid);
	build2(i * 2 + 1, mid + 1, r);
	push_up2(i);
}

node query1(ll i, ll x, ll y){
	node pp;
	pp.znum = pp.fnum = pp.pnum = 0;
	pp.zmax = 0, pp.zmin = INT_MAX, pp.fmax = INT_MIN, pp.fmin = 0;
	
	ll l = tree1[i].l, r = tree1[i].r;
	if(l == r) return tree1[i];
	
	if(l > y || r < x) return pp;
	if(x <= l && r <= y) return tree1[i];
	ll mid = (l + r) >> 1; 
	
	if(mid >= x){
		node tt = query1(i * 2, x, y);
		pp.znum += tt.znum, pp.fnum += tt.fnum, pp.pnum += tt.pnum;
		pp.zmax = max(pp.zmax, tt.zmax), pp.zmin = min(pp.zmin, tt.zmin);
		pp.fmax = max(pp.fmax, tt.fmax), pp.fmin = min(pp.fmin, tt.fmin);
	}
	if(mid < y){
		node tt = query1(i * 2 + 1, x, y);
		pp.znum += tt.znum, pp.fnum += tt.fnum, pp.pnum += tt.pnum;
		pp.zmax = max(pp.zmax, tt.zmax), pp.zmin = min(pp.zmin, tt.zmin);
		pp.fmax = max(pp.fmax, tt.fmax), pp.fmin = min(pp.fmin, tt.fmin);
	}
	return pp;
}

node query2(ll i, ll x, ll y){
	node pp;
	pp.znum = pp.fnum = pp.pnum = 0;
	pp.zmax = 0, pp.zmin = INT_MAX, pp.fmax = INT_MIN, pp.fmin = 0;
	
	ll l = tree2[i].l, r = tree2[i].r;
	if(l == r) return tree2[i];
	
	if(l > y || r < x) return pp;
	if(x <= l && r <= y) return tree2[i];
	ll mid = (l + r) >> 1; 
	
	if(mid >= x){
		node tt = query2(i * 2, x, y);
		pp.znum += tt.znum, pp.fnum += tt.fnum, pp.pnum += tt.pnum;
		pp.zmax = max(pp.zmax, tt.zmax), pp.zmin = min(pp.zmin, tt.zmin);
		pp.fmax = max(pp.fmax, tt.fmax), pp.fmin = min(pp.fmin, tt.fmin);
	}	
	if(mid < y){
		node tt = query2(i * 2 + 1, x, y);
		pp.znum += tt.znum, pp.fnum += tt.fnum, pp.pnum += tt.pnum;
		pp.zmax = max(pp.zmax, tt.zmax), pp.zmin = min(pp.zmin, tt.zmin);
		pp.fmax = max(pp.fmax, tt.fmax), pp.fmin = min(pp.fmin, tt.fmin);
	}
	return pp;
}

ll solve(ll xx1, ll yy1, ll xx2, ll yy2){
	node t1 = query1(1, xx1, yy1);
	t1.l = xx1, t1.r = yy1; t1.sz = yy1 - xx1 + 1;
	node t2 = query2(1, xx2, yy2);
	t2.l = xx2, t2.r = yy2; t2.sz = yy2 - xx2 + 1;
	
	if(t2.znum == t2.sz){
		if(t1.znum == t1.sz) return t1.zmax * t2.zmin;
		if(t1.fnum == t1.sz) return t1.fmax * t2.zmax;
		if(t1.pnum == t1.sz) return 0;
		if(!t1.fnum) return t1.zmax * t2.zmin;
		if(!t1.znum) return 0;
		if(!t1.pnum) return t1.zmax * t2.zmin;
		return t1.zmax * t2.zmin;
	}
	if(t2.fnum == t2.sz){
		if(t1.znum == t1.sz) return t1.zmin * t2.fmin;
		if(t1.fnum == t1.sz) return t1.fmin * t2.fmax;
		if(t1.pnum == t1.sz) return 0;
		if(!t1.fnum) return 0;
		if(!t1.znum) return t1.fmin * t2.fmax;
		if(!t1.pnum) return t1.fmin * t2.fmax;
		return t1.fmin * t2.fmax;
	}
	if(t2.pnum == t2.sz){
		return 0;
	}
	if(!t2.fnum){
		if(t1.fnum == t1.sz) return t1.fmax * t2.zmax;
		return 0;
	}
	if(!t2.znum){
		if(t1.znum == t1.sz) return t1.zmin * t2.fmin;
		return 0;
	}
	if(t1.znum == t1.sz) return t1.zmin * t2.fmin;
	if(t1.fnum == t1.sz) return t1.fmax * t2.zmax;
	if(!t1.pnum) return max(t1.zmin * t2.fmin, t1.fmax * t2.zmax);
	return 0;
}

int main(){
	ios::sync_with_stdio(0);
//	freopen("game.in", "r", stdin);
//	freopen("game.out", "w", stdout);
	cin >> n >> m >> q;
	for(ll i = 1; i <= n; i++) cin >> a[i];
	for(ll i = 1; i <= m; i++) cin >> b[i];
	build1(1, 1, n);
	build2(1, 1, m);
	while(q--){
		cin >> l1 >> r1 >> l2 >> r2;
		cout << solve(l1, r1, l2, r2) << endl;
	}
	return 0;
}

2022/10/29 22:33
加载中...