网站流量怎么做,做企业内刊有哪些网站推荐,wordpress 全版本注入,网站有没有做301A - Circuits
不难发现x坐标根本没用#xff0c;只需要存储y坐标。
题目所求的两条直线y1ay_1ay1a#xff0c;y2b(ab)y_2b\ (ab)y2b (ab) 我们枚举y2by_2by2b这条线#xff0c;这条线一定可以是矩形的边界#xff0c;于是我们扫描矩形边界差分计算当前…A - Circuits
不难发现x坐标根本没用只需要存储y坐标。
题目所求的两条直线y1ay_1ay1ay2b(ab)y_2b\ (ab)y2b (ab) 我们枚举y2by_2by2b这条线这条线一定可以是矩形的边界于是我们扫描矩形边界差分计算当前这条线覆盖的矩形个数对于这条线没有覆盖的矩形把它丢到线段树中维护区间和区间max即可然后区间查询y1ay_1ay1a覆盖的最大矩形即可。两种相加即是当前的情况的最大数量。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includestack
#includequeue
#includerandom
#includebitset
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
#includeunordered_set
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const ll mod998244353;
const int N200010;
int n,m;
struct line
{int id,v,op;bool operator(const line o) const{if(vo.v) return opo.op;return vo.v;}
}q[N];
int y[N];
pii a[N];
int find(int x)
{return lower_bound(y1,y1m,x)-y;
}
struct node
{int l,r;int v,lazy;}tree[N*4];
void pushup(int u)
{tree[u].vmax(tree[u1].v,tree[u1|1].v);
}
void build(int u,int l,int r)
{tree[u]{l,r};if(lr) {tree[u].v0;return;}int midlr1;build(u1,l,mid),build(u1|1,mid1,r);pushup(u);
}
void pushdown(int u)
{if(!tree[u].lazy) return;tree[u1].lazytree[u].lazy;tree[u1|1].lazytree[u].lazy;tree[u1].vtree[u].lazy;tree[u1|1].vtree[u].lazy;tree[u].lazy0;}
void modify(int u,int l,int r,int v)
{if(lr) return;if(tree[u].lltree[u].rr){tree[u].lazyv;tree[u].vv;return;}pushdown(u);int midtree[u].ltree[u].r1; ltree[u].r1;if(lmid) modify(u1,l,r,v);if(rmid) modify(u1|1,l,r,v);pushup(u);
}
int main()
{IO;int T1;//cinT;while(T--){cinn;for(int i1;in;i){int t1,t2;cint1y[i];cint2y[in];a[i]{y[in],y[i]};y[i];q[i]{i,y[i],-1};q[in]{i,y[in],1};}sort(y1,y12*n);munique(y1,y12*n)-y-1;build(1,1,m);sort(q1,q12*n);int pre0;int res0;for(int i1;i2*n;i){preq[i].op;resmax(res,pretree[1].v);if(q[i].op-1){int idq[i].id;modify(1,find(a[id].first),find(a[id].second1)-1,1);}}coutres\n;}return 0;
}这题有一个错误的贪心思路即求两边最大值。 先让第一条线覆盖最多的矩形然后把这些矩形删除然后再求出第二条线覆盖最多的矩形。
我也不知道这个贪心思路错在哪里还没举出反例 先贴一个队友写的错误代码 反例凑合看吧懂得都懂
#includecstdio
#includecstring
#includeiostream
#includecmath
#define N 20000005
using namespace std;
const int m 10000000,inf 20000000;
int n;
struct operation{int c1,c2,r1,r2;
}op[100005];
int x[N],y[N],cans1,cans2;
int read(){char ch getchar();int re 0,fl 1;while(ch0||ch9) {if(fl -)fl -1; ch getchar();}while(ch0ch9) {re (re1)(re3)ch-0; ch getchar();}return re*fl;
}
int main(){//freopen(1.in,r,stdin); int r1,r2,c1,c2,rf inf,rl 0,cf inf,cl 0;int pre 0,fd 0; n read();for(int i1;in;i){r1 read()m; c1 read()m;//r1r2 c1c2r2 read()m; c2 read()m;y[c11]--; y[c2];op[i].c1 c1; op[i].c2 c2; op[i].r1 r1; op[i].r2 r2;}pre 0; fd -1;for(int i0;i2*m;i){pre y[i];if(pre cans1){cans1 pre; fd i;}}for(int i1;in;i)if(op[i].c1 fd op[i].c2 fd){y[op[i].c11]; y[op[i].c2]--;}pre 0;for(int i0;i2*m;i){pre y[i];cans2 max(cans2,pre);}printf(%d\n,cans1cans2);return 0;
}
