COGS：1822. [AHOI2013]作业

1822. [AHOI 2013] 作业

★★★ 输入文件：ahoi2013_homework.in 输出文件：ahoi2013_homework.out 简单对比
时间限制：20 s 内存限制：512 MB

【题目描述】

【输入格式】

【输出格式】

【样例输入】

3 4

1 2 2

1 2 1 3

1 2 1 1

1 3 1 3

2 3 2 3

【样例输出】

2 2

1 1

3 2

2 1

【提示】

N=100000,M=1000000

数据极弱（和BZOJ相比），请放心A

【来源】

BZOJ 3236

分析

莫队，用树状数组来维护求值，一个求出现不同数的个数，另一个满足的数字个数。复杂度$O(nsqrt n log_2n)$

另一种做法：由于这些数都是小于等于n的，所以对权值进行分块，修改$O(1)$，查询$O(sqrt n)$，总复杂度$O(m sqrt n)$

交了几次，最后一个点老是TLE，然后想尽办法，读入优化，inline内联函数，最后写上了输出优化。。。还是TLE，之后才发现ans数组开小了，直接开了MAXN，QAQ

代码

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cmath>
  4 using namespace std;
  5  
  6 const int MAXN = 100100;
  7 struct Que{
  8     int l,r,a,b,block,id;
  9     bool operator < (const Que &a) const 
 10     {
 11         if (block==a.block) return r < a.r;
 12         return block < a.block;
 13     }
 14 }q[1000100];
 15 int a[MAXN],cnt[MAXN],tr[2][MAXN],pr[15];
 16 int ans1[1000100],ans2[1000100];
 17 int n,m,pos,len;
 18 
 19 inline int read()
 20 {
 21     int x=0,f=1;char ch=getchar();
 22     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 23     while(ch>='0'&& ch<='9'){x=x*10+ch-'0';ch=getchar();}
 24     return x*f;
 25 }
 26 inline int lowbit(int x)
 27 {
 28     return x & (-x);
 29 }
 30 inline void change(int x,int c,int t)
 31 {
 32     while (x<=n)
 33     {
 34         tr[t][x] += c;
 35         x += lowbit(x);
 36     }
 37 }
 38 inline int query(int x,int t)
 39 {
 40     int res = 0;
 41     while (x)
 42     {
 43         res += tr[t][x];
 44         x -= lowbit(x);
 45     }
 46     return res;
 47 }
 48 inline void update(int x,int c)
 49 {
 50     if (cnt[x]==0) change(x,1,1);
 51     cnt[x] += c;
 52     if (cnt[x]==0) change(x,-1,1);
 53     change(x,c,0);
 54 }
 55 inline void solve()
 56 {
 57     int l = 1, r = 0;
 58     for (int i=1; i<=m; ++i)
 59     {
 60         for (; l>q[i].l; ) update(a[--l], 1);
 61         for (; r<q[i].r; ) update(a[++r], 1);
 62         for (; l<q[i].l; ) update(a[l++], -1);
 63         for (; r>q[i].r; ) update(a[r--], -1);
 64         ans1[q[i].id] = query(q[i].b, 0) - query(q[i].a-1, 0);
 65         ans2[q[i].id] = query(q[i].b, 1) - query(q[i].a-1, 1);
 66     }
 67 }
 68 inline void print(int x) 
 69 {
 70     while (x)
 71         pr[++len] = x%10, x/=10;
 72     if (!len) putchar('0');
 73     while (len)
 74         putchar(pr[len--]+'0');
 75 }
 76 int main()
 77 {
 78     freopen("ahoi2013_homework.in","r",stdin);
 79     freopen("ahoi2013_homework.out","w",stdout);
 80     n = read(); m = read();
 81     pos = (int)sqrt(n);
 82     for (int i=1; i<=n; ++i)
 83         a[i] = read();
 84     for (int i=1; i<=m; ++i)
 85     {
 86         q[i].l = read(); q[i].r = read();
 87         q[i].a = read(); q[i].b = read();
 88         q[i].block = (q[i].l-1)/pos+1;
 89         q[i].id = i;
 90     }
 91     sort(q+1,q+m+1);
 92     solve();
 93     for (int i=1; i<=m; ++i)
 94     {
 95         print(ans1[i]),putchar(' ');
 96         print(ans2[i]),putchar('
');
 97         //printf("%d %d
",ans1[i],ans2[i]);
 98     }
 99     return 0;
100 }