毕业设计做网站教程,cms系统排行榜,流程做网站,谁用fun域名做网站了题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/370/A 来源#xff1a;牛客网
恭喜你找到了本场比赛的签到题#xff01; 为了让大家都有抽奖的机会#xff0c;只需要复制粘贴以下代码#xff08;并且稍微填下空#xff09;即可 AC#xff1…题干
链接https://ac.nowcoder.com/acm/contest/370/A 来源牛客网
恭喜你找到了本场比赛的签到题 为了让大家都有抽奖的机会只需要复制粘贴以下代码并且稍微填下空即可 AC 我超良心的
#include algorithm#include iostream#include cstring#include climits#include cstdio#include vector#include cstdlib#include ctime#include cmath#include queue#include stack#include map#include set#define fi first#define lc (x1)#define se second#define U unsigned#define rc (x1|1)#define Re register#define LL long long#define MP std::make_pair#define CLR(i,a) memset(i,a,sizeof(i))#define FOR(i,a,b) for(Re int i a;i b;i)#define ROF(i,a,b) for(Re int i a;i b;--i)#define SFOR(i,a,b,c) for(Re int i a;i b;ic)#define SROF(i,a,b,c) for(Re int i a;i b;i-c)#define DEBUG(x) std::cerr #x x std::endlconst int MAXN 10000005;int N,maxL;std::setstd::pairint,int L;inline int calc(){// 返回 set 中所有线段的并长度。(每个 pair 表示一个线段[first,second]}int main(){scanf(%d%d,N,maxL);while(N--){int opt,x,y;scanf(%d%d%d,opt,x,y);if(opt 1){if(L.find(MP(x,y)) ! L.end()) continue;L.insert(MP(x,y));}if(opt 2){if(L.find(MP(x,y)) L.end()) continue;L.erase(MP(x,y));}if(opt 3){printf(%d\n,calc());}}return 0;}
输入描述:
第一行两个整数 N,L意义如代码所述。接下来 N 行每行三个整数 opt,l,r意义如代码所述。
输出描述:
对于每一组 opt3 的询问输出一个答案。
示例1
输入
复制
6 13
1 1 2
1 4 5
1 4 7
1 6 9
1 12 13
3 3 3
输出
复制
10
说明
我们依次加入线段[1,2],[4,5],[4,7],[6,9],[12,13] 它们的并集长度为 10.
备注:
N≤105,L≤105,0≤l≤r≤LN≤105,L≤105,0≤l≤r≤L保证数据随机生成。
解题报告
题目需要你维护一个线段集合支持插入线段删除线段和求线段并长度。
我们可以用简化版的扫描线来实现当然因为数据随机暴力也可以过。。。。
AC代码1直接暴力400ms-800ms
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 1e5 5;
setint ss[MAX];
int vis[MAX];
int main()
{int n,maxl,ans0;scanf(%d%d, n, maxl);for(int i 1; in; i) {int op,l,r;scanf(%d%d%d,op,l,r);if(l r) swap(l,r);if(op 1) {if(ss[l].find(r)!ss[l].end()) continue;ss[l].insert(r);for(int j l; jr; j) {if(vis[j] 0) ans;vis[j];}}if(op 2) {if (ss[l].find(r)ss[l].end()) continue;ss[l].erase(r);for(int j l; jr; j) {if(vis[j] 1) ans--;vis[j]--;}}if(op 3) printf(%d\n,ans);}return 0 ;}
AC代码2扫描线100ms
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
setint s[100005];
struct Tree {int l,r;int val;int laz;
} tree[100005 * 4];
inline int len(int cur) {return tree[cur].r - tree[cur].l 1;
}
void pushup(int cur) {if(tree[cur].laz 0) tree[cur].val len(cur);else if (tree[cur].l tree[cur].r) tree[cur].val 0;else tree[cur].val tree[cur*2].val tree[cur*21].val;
}
void pushdown(int cur) {if(tree[cur].laz 0) return ;tree[cur*2].laz tree[cur].laz;tree[cur*21].laz tree[cur].laz;tree[cur*2].val tree[cur].laz;tree[cur*21].val tree[cur].laz;tree[cur].laz 0;
}
void build(int l,int r,int cur) {tree[cur].val0;tree[cur].l l;tree[cur].r r;if(l r) return ;int m (lr)1;build(l,m,cur*2);build(m1,r,cur*21);
}
void update(int pl,int pr,int val,int cur) {if(pl tree[cur].l pr tree[cur].r) {tree[cur].laz val;pushup(cur);return ;}//pushdown(cur);if(tree[cur*2].r pl) update(pl,pr,val,cur*2);if(tree[cur*21].l pr) update(pl,pr,val,cur*21);pushup(cur);
}
int main() {int ans0,N,maxL;scanf(%d%d, N, maxL);build(1,maxL,1);while (N--) {int opt, x, y;scanf(%d%d%d, opt, x, y);if (xy) swap(x,y);if (opt 1) {if (s[x].find(y)!s[x].end()) continue;s[x].insert(y);update(x,y,1,1);}if (opt 2) {if (s[x].find(y)s[x].end()) continue;s[x].erase(y); update(x,y,-1,1);}if (opt 3) {printf(%d\n, tree[1].val);}}return 0;
}
AC代码3扫描线pushdown版本应该是可以支持区间覆盖情况查询的
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
setint s[100005];
struct Tree {int l,r;int val;int laz;
} tree[100005 * 4];
inline int len(int cur) {return tree[cur].r - tree[cur].l 1;
}
void pushup(int cur) {if(tree[cur].laz 0) tree[cur].val len(cur);else if (tree[cur].l tree[cur].r) tree[cur].val 0;else tree[cur].val tree[cur*2].val tree[cur*21].val;
}
void pushdown(int cur) {if(tree[cur].laz 0) return ;tree[cur*2].laz tree[cur].laz;tree[cur*21].laz tree[cur].laz;
// tree[cur*2].val tree[cur].laz;
// tree[cur*21].val tree[cur].laz;
// tree[cur].laz 0;
}
void build(int l,int r,int cur) {tree[cur].val0;tree[cur].l l;tree[cur].r r;if(l r) return ;int m (lr)1;build(l,m,cur*2);build(m1,r,cur*21);
}
void update(int pl,int pr,int val,int cur) {if(pl tree[cur].l pr tree[cur].r) {tree[cur].laz val;pushup(cur);return ;}pushdown(cur);if(tree[cur*2].r pl) update(pl,pr,val,cur*2);if(tree[cur*21].l pr) update(pl,pr,val,cur*21);pushup(cur);
}
int main() {int ans0,N,maxL;scanf(%d%d, N, maxL);build(1,maxL,1);while (N--) {int opt, x, y;scanf(%d%d%d, opt, x, y);if (xy) swap(x,y);if (opt 1) {if (s[x].find(y)!s[x].end()) continue;s[x].insert(y);update(x,y,1,1);}if (opt 2) {if (s[x].find(y)s[x].end()) continue;s[x].erase(y); update(x,y,-1,1);}if (opt 3) {printf(%d\n, tree[1].val);}}return 0;
}
标程 我们考虑一种非常暴力的做法对于这个数轴建出线段树然后插入删除对应了区间加值操作。 我们来考虑一下询问操作最朴素的方法是查询每个点是否有值然后统计答案。我们可以考虑对每一个线段树上的节点维护一个 min 值这样遍历到一个节点的时候如果当前节点的 min 0 那么说明这个线段树节点对应的区间是所有线段并的一部分。 当然这样的话还是不一定能过的但是注意到数据随机生成所以查询操作仅为总操作的1313 且删除操作大概率不会触发。
const int MAXN 1000005;
#define lc (x1)
#define rc (x1|1)
int min[MAXN2],tag[MAXN2];inline void pushup(int x){min[x] std::min(min[lc],min[rc]);
}inline void cover(int x,int l,int r,int delta){min[x] delta;tag[x] delta;
}inline void pushdown(int x,int l,int r){if(tag[x]){int mid (l r) 1;cover(lc,l,mid,tag[x]);cover(rc,mid1,r,tag[x]);tag[x] 0;}
}inline void modify(int x,int l,int r,int L,int R,int delta){if(l L R r){cover(x,l,r,delta);return;}pushdown(x,l,r);int mid (l r) 1;if(R mid) modify(lc,l,mid,L,R,delta);else if(L mid) modify(rc,mid1,r,L,R,delta);else modify(lc,l,mid,L,mid,delta),modify(rc,mid1,r,mid1,R,delta);pushup(x);
}inline int query(int x,int l,int r){if(min[x] ! 0) return r-l1;if(l r) return min[x] ! 0;int mid (l r) 1;pushdown(x,l,r);return query(lc,l,mid)query(rc,mid1,r);
}std::mapP,bool S;
int L 0;
int main(){int N;scanf(%d%d,N,L);while(N--){int opt,x,y;scanf(%d%d%d,opt,x,y);if(opt 1){if(S[MP(x,y)]) continue;S[MP(x,y)] true;// L std::max(L,y);modify(1,1,L,x,y,1);}if(opt 2){if(!S[MP(x,y)]) continue;S[MP(x,y)] false;modify(1,1,L,x,y,-1);}if(opt 3){printf(%d\n,query(1,1,L));}}return 0;
}
