云南云南省城乡建设厅网站,互联网保险经纪公司排名,wordpress数据库字典,互联网设计师题目描述 Bytetown城市要进行市长竞选#xff0c;所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理#xff0c;城市委员会为选民准备了一个张贴海报的electoral墙。 张贴规则如下#xff1a; electoral墙是一个长度为N个单位的长方形#xff0c;每个单位… 题目描述 Bytetown城市要进行市长竞选所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理城市委员会为选民准备了一个张贴海报的electoral墙。 张贴规则如下 electoral墙是一个长度为N个单位的长方形每个单位记为一个格子 所有张贴的海报的高度必须与electoral墙的高度一致的 每张海报以“A B”表示即从第A个格子到第B个格子张贴海报 后贴的海报可以覆盖前面已贴的海报或部分海报。 现在请你判断张贴完所有海报后在electoral墙上还可以看见多少张海报。 输入输出格式 输入格式 第一行 N M 分别表示electoral墙的长度和海报个数 接下来M行: Ai Bi 表示每张海报张贴的位置 输出格式 输出贴完所有海报后在electoral墙上还可以看见的海报数。 输入输出样例 输入样例#1 复制 100 5
1 4
2 6
8 10
3 4
7 10输出样例#1 复制 4 说明 【约束条件】 1 0 N 10000000 1M1000 1 Ai Bi 10000000 所有的数据都是整数。数据之间有一个空格 数据太大要进行离散化 然后区间染色 query有一点不一样 必须要读到叶结点 然后统计颜色即可 #includebits/stdc.h
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i(a);i(b);i)
#define repp(i,a,b) for(int i(a);i(b);--i)
#define RI(n) scanf(%d,(n))
#define RII(n,m) scanf(%d%d,n,m)
#define RIII(n,m,k) scanf(%d%d%d,n,m,k)
#define RS(s) scanf(%s,s);
#define ll long long
#define pb push_back
#define CLR(A,v) memset(A,v,sizeof A)
//
#define inf 0x3f3f3f3f
#define lson l,m,pos1
#define rson m1,r,pos1|1
const int N1000005;
int sum[N2],col[N2],tot[N2];
int n,L[N],R[N],a[N],cnt,len,vis[N],ans;int find1(int L,int R,int x)
{while(LR){int m(LR)1;if(a[m]x)return m;else if(a[m]x)Rm-1;else Lm1;}
}
void down(int pos)
{if(sum[pos]){sum[pos1]sum[pos1|1]col[pos];col[pos1]col[pos1|1]col[pos];sum[pos]0;}
}
void update(int L,int R,int v,int l,int r,int pos)
{if(LlrR){sum[pos]col[pos]v;return ;}down(pos);int m(lr)1;if(Lm)update(L,R,v,lson);if(Rm)update(L,R,v,rson);
}
void query(int L,int R,int l,int r,int pos)
{if(lr){tot[sum[pos]];return ;}down(pos);int m(lr)1;if(Lm)query(L,R,lson);if(Rm)query(L,R,rson);
}int main()
{RI(n);int m;RI(m);rep(i,1,m){RII(L[i],R[i]);a[cnt]L[i];a[cnt]R[i];}sort(a1,a1cnt);len1;rep(i,2,cnt)if(a[i]!a[i-1])a[len]a[i];repp(i,len,2)if(a[i]-a[i-1]1)a[len]a[i]-1;sort(a1,a1len);rep(i,1,m){int lfind1(1,len,L[i]);int rfind1(1,len,R[i]);update(l,r,i,1,len,1);}query(1,len,1,len,1);ans0;rep(i,1,m)if(tot[i])ans;coutans;return 0;
} View Code 转载于:https://www.cnblogs.com/bxd123/p/10895836.html
