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 ;
}

最新文章

  1. Linux安装DBI/DBD-ORACLE
  2. Odoo Graph 指定默认 类型
  3. c#中委托和事件(续)(转)
  4. Hashtable HashMap
  5. Spark基础与Java Api介绍
  6. 制作简易计算器处理结果Servlet
  7. curl要注意的几点
  8. 【Python】分布式任务队列Celery使用参考资料
  9. nginx install
  10. Qt 5.x 全局热键 for windows
  11. powershell 统计AD中所有计算机及对应的操作系统信息
  12. SSH深度历险(十) AOP原理及相关概念学习+AspectJ注解方式配置spring AOP
  13. Forth 文本解释程序
  14. 关于jfinal发送邮件走过的坑
  15. Python-序列化模块-json-62
  16. java List&lt;Map&lt;String,Object&gt;
  17. Java链式异常
  18. xpath教程 3 - xpath的小结
  19. vim文本处理技巧
  20. Django 1.10.2 模型数据库操作

热门文章

  1. 组播报文转发过程RPF
  2. 有关UITableViewCell的侧滑删除以及使用相关大神框架MGSwipeTableCell遇到的小问题
  3. [置顶] NO.4 使用预处理器进行调试
  4. [React Testing] The Redux Store - Multiple Actions
  5. Android 基于Netty的消息推送方案之Hello World(一)
  6. Stack and queue.
  7. Visual Studio Code使用typings拓展自动补全功能
  8. 如何改写WebApi部分默认规则
  9. C++ 知识点1
  10. Python新手学习基础之初识python——与众不同1