3236: [Ahoi2013]作业

Time Limit: 100 Sec  Memory Limit: 512 MB
Submit: 1393  Solved: 562
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

3 4
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3

Sample Output

2 2
1 1
3 2
2 1

HINT

N=100000,M=1000000

Source

[Submit][Status][Discuss]

莫队算法 + 树状数组统计答案

 #include <cmath>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /* SCANNER */

 #define siz 10000000

 inline char get_a(void) {

     static char buf[siz], *bit = buf;

     if (bit == buf + siz)

         fread(bit = buf, , siz, stdin);

     return *bit++;

 }

 inline int get_i(void) {

     register int ret = ;

     register int neg = false;

     register int bit = get_a();

     for (; bit < ''; bit = get_a())

         if (bit == '-')neg ^= true;

     for (; bit >= ''; bit = get_a())

         ret = ret *  + bit - '';

     return neg ? -ret : ret;

 }

 #define maxn 400005

 #define maxm 1000005

 int s;

 int tot;

 int n, m;

 int num[maxn];

 int cnt[maxn];

 int tmp[maxn];

 int ans1[maxm];

 int ans2[maxm];

 int tree1[maxn];

 int tree2[maxn];

 struct query {

     int l, r, a, b, id;

 }qry[maxm];

 inline int cmp(const void *a, const void *b) {

     query *A = (query *)a;

     query *B = (query *)b;

     if (A->l / s != B->l / s)

         return A->l - B->l;

     else

         return A->r - B->r;

 }

 inline void add(int *t, int p, int k) {

     for (; p <= tot; p += p&-p)

         t[p] += k;

 }

 inline int ask(int *t, int p) {

     int ret = ;

     for (; p; p -= p&-p)

         ret += t[p];

     return ret;

 }

 inline void remove(int t) {

     add(tree1, t, -);

     if (--cnt[t] == )

         add(tree2, t, -);

 }

 inline void insert(int t) {

     add(tree1, t, );

     if (++cnt[t] == )

         add(tree2, t, );

 }

 signed main(void) {

     n = get_i();

     m = get_i();

     s = sqrt(n);

     for (int i = ; i <= n; ++i)

         num[i] = get_i(), tmp[++tot] = num[i];

     for (int i = ; i <= m; ++i) {

         qry[i].id = i;

         qry[i].l = get_i();

         qry[i].r = get_i();

         qry[i].a = get_i();

         qry[i].b = get_i();

     }

     for (int i = ; i <= m; ++i)

         tmp[++tot] = qry[i].a,

         tmp[++tot] = qry[i].b;

     sort(tmp + , tmp +  + tot);

     tot = unique(tmp + , tmp +  + tot) - tmp;

     for (int i = ; i <= n; ++i)

         num[i] = lower_bound(tmp + , tmp + tot, num[i]) - tmp;

     for (int i = ; i <= m; ++i) {

         qry[i].a = lower_bound(tmp + , tmp + tot, qry[i].a) - tmp;

         qry[i].b = lower_bound(tmp + , tmp + tot, qry[i].b) - tmp;

     }

     /*

     for (int i = 1; i <= n; ++i)

         printf("%d ", num[i]);

     puts("");

     for (int i = 1; i <= m; ++i)

         printf("%d %d\n", qry[i].a, qry[i].b);

     */

     qsort(qry + , m, sizeof(query), cmp);

     int l = , r = ;

     for (int i = ; i <= m; ++i) {

         while (l < qry[i].l)remove(num[l++]);

         while (l > qry[i].l)insert(num[--l]);

         while (r < qry[i].r)insert(num[++r]);

         while (r > qry[i].r)remove(num[r--]);

         ans1[qry[i].id] = ask(tree1, qry[i].b) - ask(tree1, qry[i].a - );

         ans2[qry[i].id] = ask(tree2, qry[i].b) - ask(tree2, qry[i].a - );

     }

     for (int i = ; i <= m; ++i)

         printf("%d %d\n", ans1[i], ans2[i]);

     //system("pause");

 }
 #include <cmath>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /* SCANNER */

 #define siz 50000000

 inline int get_c(void)

 {

     static char buf[siz];

     static char *head = buf;

     static char *tail = buf + siz;

     if (head == tail)

         fread(head = buf, , siz, stdin);

     return *head++;

 }

     #define getc get_c

 //    #define getc getchar

 inline int get_i(void)

 {

     register int ret = ;

     register int neg = false;

     register int bit = getc();

     for (; bit < ''; bit = getc())

         if (bit == '-')neg ^= true;

     for (; bit >= ''; bit = getc())

         ret = ret *  + bit - '';

     return neg ? -ret : ret;

 }

 /* PROBLEM */

 #define maxn 100005

 #define maxm 1000005

 int n, m, s;

 int num[maxn];

 int cnt[maxm * ];

 int tmp[maxm * ];

 int *tot = tmp + ;

 int tree1[maxm * ];

 int tree2[maxm * ];

 /* QRY */

 struct query

 {

     int l, r;

     int a, b;

     int ans1;

     int ans2;

 }qry[maxm], *ord[maxm];

 inline bool cmp(query *a, query *b)

 {

     if (a->l / s != b->l / s)

         return a->l < b->l;

     else

         return a->r < b->r;

 }

 /* BIT */

 inline void add(int *t, int p, int k)

 {

     int len = tot - tmp;

     for (; p <= len; p += p&-p)

         t[p] += k;

 }

 inline int ask(int *t, int p)

 {

     int ret = ;

     for (; p; p -= p&-p)

         ret += t[p];

     return ret;

 }

 /* MOQ */

 inline void insert(int t)

 {

     add(tree1, t, +);

     if (++cnt[t] == )

         add(tree2, t, +);

 }

 inline void remove(int t)

 {

     add(tree1, t, -);

     if (--cnt[t] == )

         add(tree2, t, -);

 }

 /* MAIN */

 signed main(void)

 {

     n = get_i();

     m = get_i();

     s = sqrt(n);

     for (int i = ; i <= n; ++i)

         *tot++ = num[i] = get_i();

     for (int i = ; i <= m; ++i)

     {

         ord[i] = qry + i;

         qry[i].l = get_i();

         qry[i].r = get_i();

         *tot++ = qry[i].a = get_i();

         *tot++ = qry[i].b = get_i();

     }

     sort(tmp + , tot); 

     tot = unique(tmp + , tot);

     for (int i = ; i <= n; ++i)

         num[i] = lower_bound(tmp + , tot, num[i]) - tmp;

     for (int i = ; i <= m; ++i)

     {

         qry[i].a = lower_bound(tmp + , tot, qry[i].a) - tmp;

         qry[i].b = lower_bound(tmp + , tot, qry[i].b) - tmp;

     }

     sort(ord + , ord +  + m, cmp);

     int lt = , rt = ;    // left & right

     for (int i = ; i <= m; ++i)

     {

         query *q = ord[i];

         while (lt < q->l)remove(num[lt++]);

         while (lt > q->l)insert(num[--lt]);

         while (rt < q->r)insert(num[++rt]);

         while (rt > q->r)remove(num[rt--]);

         q->ans1 = ask(tree1, q->b) - ask(tree1, q->a - );

         q->ans2 = ask(tree2, q->b) - ask(tree2, q->a - );

     }

     for (int i = ; i <= m; ++i)

         printf("%d %d\n", qry[i].ans1, qry[i].ans2);

     //system("pause");

 }

@Author: YouSiki

最新文章

  1. itput
  2. MQ介绍
  3. oracle 执行执行动态存储过程名---其实就是存储过程名是个字符串参数
  4. Python的交互式界面 编写 .
  5. C. Tourist's Notes
  6. 《OD大数据实战》Hadoop伪分布式环境搭建
  7. Oracle EBS 如何月结[Z]
  8. hadoop笔记之Hive的数据存储(外部表)
  9. python语言学习7——数据类型和变量
  10. 使用Canvas基于手势可以使树秋千
  11. PID控制学习笔记（一）
  12. ffmpeg合并多个视频
  13. 201521123070 《JAVA程序设计》第14周学习总结
  14. Uva 11300 Spreading the Wealth(递推，中位数)
  15. 一位IT男的7年工作经验总结
  16. 借鉴mini2440的usb-wifi工具集在Beagleboard上移植无线网卡
  17. Hibernate（十三）：HQL查询（二）
  18. [CTSC2017]网络
  19. C++实现多级排序
  20. dns相关

热门文章

  1. C语言关于利用sscanf实现字符串相加减
  2. Django入门
  3. Oracle索引梳理系列（七）- Oracle唯一索引、普通索引及约束的关系
  4. 遇到shell重定向的一个奇怪问题：&#39;消失&#39;的标准输入！
  5. 安装Ubuntu的那些事儿（续）
  6. eclipse配置tomcat出现错误：Could not load the Tomcat server configuration at \Servers\Tomcat v7.0 Server at localhost-config.
  7. js快速判断IE浏览器(兼容IE10与IE11)
  8. Eclipse不自动编译java文件的终极解决方案
  9. netty3升netty4一失眼成千古恨
  10. CF724B. Batch Sort[枚举]