Codeforce 216 div2
2024-10-19 00:21:36
D
只要搞清楚一个性质:确定了当前最大和次大的位置,局面就唯一确定了;
根据这个性质设计dp,统计到达该局面的方法数即可.
E
询问的要求是: 求有多少个区间至少覆盖了询问的点集中的一个;
转化成逆命题比较好算: 算出排好序后相邻的点之间有多少个完整区间,再用n减去它.
于是问题转化为回答若干询问[l,r] ,它当中有多少个完整的区间.
可以用经典的离线+树状数组来做.
#define rep(i,n) for(int i=0 ; i<(n) ; i++ )
#define ls ((rt)<<1)
#define rs (((rt)<<1)+1)
#define mid ((l+r)>>1)
#define maxn 1000002
struct node
{
int id,lft;
};vector<node>q[maxn];
vector<int>l[maxn];
int sum[maxn],ans[],n,m,cnt[];
int lowbit(int x) {return x&(-x);}
void add(int pos,int var)
{
for (int i=pos ; i<maxn ; i+=lowbit(i)) sum[i]+=var;
}
int query(int pos)
{
int res=;
for (int i=pos ; i> ; i-=lowbit(i)) res+=sum[i];
return res;
}
int main()
{
scanf("%d%d",&n,&m);
rep(i,n)
{
int lft,rgt;
scanf("%d%d",&lft,&rgt);
l[rgt].push_back(lft);
}
rep(i,m)
{
int sz;
scanf("%d",&sz);
rep(j,sz) scanf("%d",&cnt[j]);
int lft,rgt;
lft=,rgt=cnt[]-;
q[rgt].push_back((node){i,lft});
rep(j,sz-)
{
lft=cnt[j]+;
rgt=cnt[j+]-;
if (lft<=rgt) q[rgt].push_back((node){i,lft});
}
lft=cnt[sz-]+,rgt=;
q[rgt].push_back((node){i,lft});
}
rep(i,maxn)
{
rep(j,(int)l[i].size())
{
int pos = l[i][j];
add(pos,);
}
rep(j,(int)q[i].size())
{
int id = q[i][j].id;
ans[id] += query(i)-query(q[i][j].lft-);
}
}
rep(i,m) printf("%d\n",n-ans[i]);
return ;
}
最新文章
- Linux安装DBI/DBD-ORACLE
- Odoo Graph 指定默认 类型
- c#中委托和事件(续)(转)
- Hashtable HashMap
- Spark基础与Java Api介绍
- 制作简易计算器处理结果Servlet
- curl要注意的几点
- 【Python】分布式任务队列Celery使用参考资料
- nginx install
- Qt 5.x 全局热键 for windows
- powershell 统计AD中所有计算机及对应的操作系统信息
- SSH深度历险(十) AOP原理及相关概念学习+AspectJ注解方式配置spring AOP
- Forth 文本解释程序
- 关于jfinal发送邮件走过的坑
- Python-序列化模块-json-62
- java List<;Map<;String,Object>;
- Java链式异常
- xpath教程 3 - xpath的小结
- vim文本处理技巧
- Django 1.10.2 模型数据库操作
热门文章
- 组播报文转发过程RPF
- 有关UITableViewCell的侧滑删除以及使用相关大神框架MGSwipeTableCell遇到的小问题
- [置顶] NO.4 使用预处理器进行调试
- [React Testing] The Redux Store - Multiple Actions
- Android 基于Netty的消息推送方案之Hello World(一)
- Stack and queue.
- Visual Studio Code使用typings拓展自动补全功能
- 如何改写WebApi部分默认规则
- C++ 知识点1
- Python新手学习基础之初识python——与众不同1