讨论下这几种算法[寻高效的算法]

Susake_

设置成悬赏贴好了(20就封顶了)
下面的数据量就当作10^5处理吧^_^第一楼就用来贴题目！
问题一.有一序列a1,a2,a3,a4......an,查询序列中比ai大的有几个？(一维)------------------------------------------------
输入
5               //有n个数
2 2 3 4 1    //每个数分别为ai
2               //查询次数
2               //第1次
4               //第2次
输出
2              //第一次查询结果
0              //第二次查询结果
问题二.有一个序列数a1,a2,a3,a4......an;查询序列中满足比ai大且比bi大的有几个?(二维)-----------------------------------------
                          b1,b2,b3,b4......bn;
输入
4            //有n组数
1 2         //第i的ai bi      
2 3
1 3
3 5
2          //m次查询
2 3       //第一次
1 2       //第二次
输出
1         //第一次查询结果
2         //第二次查询结果
问题三.有一序列数a1,a2,a3,a4......an;查询序列中满足比ai大且比bi大&&比ci大的有几个?(三维)------------------------------------
                       b1,b2,b3,b4......bn;
                       c1,c2,c3,c4......cn;

....和问题一,二的输入形式差不多~~
问题四.有一系列操作指令,a代表+,d代表-,q代表查询(一维)--------------------------------------------------
输入
6                 //有n次操作指令
a a1 2           //让a1+2          此时a1=2        (所以ai初始状态为0)
a a1 3           //让a1再+3       此时a1=5
a a2 1          //让a2+1           此时a2=1
d a1 1          //让a1-1            此时a1=4
q a1            //查询并输出a1的值    4---------------编辑见下
q a2            //查询兵输出a2的值    1---------------编辑见下
应该是
q a1 a2       //查询a1 a2区间的数的个数   (嗯,这问题的解法是树状数组,同hdc1166)
问题五.大编辑了一下
就是问题二未改动前的模型见5楼
删除了问题6
挺纠结的几个问题，各位有没有好的思路？谢谢哈！！

Kurosaki_Ichigo

呵呵关于第二题你在1楼的描述与6楼原题的描述相差很多。

1楼中ai与bi是两个独立因子，两者间没有任何联系。而6楼中它们是作为一个区间的两个边界，这使得两者间存在一个隐含条件：左界小于等于右边界。

当然题目可以不设定a必然是左边界、b必然是右边界，这可以在程序中判定并调整为a是左边界、b是右边界。

这里就讨论一下6楼原题的解决办法吧，并假定输入的a必然是左边界、b必然是右边界（不假定的情况只需要在读取后调整一下即可），而且区间是闭区间。

这时只需要优先按左边界其次按右边界对区间元素进行升序排序，然后分别按左边界和右边界二分检索出两个元素。

那么这两个元素之间的元素必然落入之前检索出的两个边界之内。

这里还需要就闭区间的包含关系说明一下。举例：

两个区间[1, 2]、[1,3]，认为是[1,3]包含[1,2]。而两个相同的区间（如[1,2]、[1,2]）认为是相互包含的。

下面是实现上面描述的代码。说明的一点是代码中检索左右边界元素时得到的左边界元素为左边界内侧最右边的元素，右边界元素为右边界外侧最左边的元素。

按照6楼描述的输出结果，输出的顺序是与输入区间的顺序对应的，所以排序过程中要带着元素的原索引。

这里我用数组s来存储区间元素，s[0]为原元素索引，s[1]为元素左边界，s[2]为元素右边界。

具体看代码吧。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define M(x) (*(int (*)[3])(x))
   
5. 
   
6. int cmp(const void * a, const void * b)
   
7. {
   
8.         return M(a)[1] != M(b)[1] ? M(a)[1] - M(b)[1] : M(a)[2] - M(b)[2];
   
9. }
   
10. 
    
11. int search(int (*s)[3], int n, int id)
    
12. {
    
13.         int L, R, i, t;
    
14. 
    
15.         for(L = 0, i = n; L < i; s[t=(L+i)/2][1] < s[id][1] ? (L=t+1) : (i=t));
    
16.         for(R = 0, i = n; R < i; s[t=(R+i)/2][2] <= s[id][2] ? (R=t+1) : (i=t));
    
17.         return R - L - 1;
    
18. }
    
19. 
    
20. int main()
    
21. {
    
22.         int (*s)[3], *r, n, i;
    
23. 
    
24.         scanf("%d", &n);
    
25.         s = (int (*)[3])malloc(sizeof(s[0]) * n);
    
26.         r = (int *)malloc(sizeof(r[0]) * n);
    
27.         for(i = -1; ++i < n; s[i][0] = i) scanf("%d%d", &s[i][1], &s[i][2]);
    
28.         qsort(s, n, sizeof(s[0]), cmp);
    
29.         for(i = -1; ++i < n; r[s[i][0]] = search(s, n, i));
    
30.         for(printf("%d", r[i = 0]); ++i < n; printf(" %d", r[i]));
    
31.         putchar('\n');
    
32.         free(s);
    
33.         free(r);
    
34.         return 0;
    
35. }

复制代码

关于第三题待我有时间去CF实际提交一下再说。

Susake_

上面的题目都是自己想的，没有验证地址！
第一题暂时想到的是二分~代码等下补上--[编辑]二分好像也不行,找的目标值不确定!还是直接for吧..--

Kurosaki_Ichigo

问题一到三是一个问题，排序后二分查找没有问题（一到三只是比较函数不同而已）。当然不能直接用bsearch库函数，需要自己写一个。

问题四按着题意简单顺序操作即可。

问题五我有点疑问，这个区间是个什么概念？针对例子中q a1 b1的输出结果是4，那我下面的例子结果该是什么？

a a1 b2 1
a a2 b2 1
q a1 b2
q a2 b2

folklore

终于没看懂楼主在说什么， 题目好像是看懂了， 加上说明就不懂了。

1. 上面的题目都是自己想的，没有验证地址！
   
2. 第一题暂时想到的是二分~代码等下补上--[编辑]二分好像也不行,找的目标值不确定!还是直接for吧..--
   

复制代码

第123都只能遍历， 题目本身就是要求要遍历的， 最小复杂度都是n,  n-1都不行， 除非成就上仙了果位。

wangell2012

所有的问题都可以看成数组来处理, 直接对数组进行扫描就可以了.

Susake_

回复 3# Kurosaki_Ichigo
刚刚回复没成功，又重打一遍T_T
先说说前3题
第一题是额外加的
第二题是前段时间碰到的一个问题,但题目的名字忘了
那题的题意是给你n组ai,bi,让你找出比ai大但比bi小的组的个数【反复看了一下好像雷同原先的问题5】
(这里我改成了比ai且比bi大,如果改了题意完全变了那就sorry了)
那题大大意是
先给你4(n)组ai,bi
1 10    即在[1,10]区间的是[2,6],[3,5],[4,7]三组
2 6         在[2,6]区间的是[3,5]
3 5         在[3,5]区间没有
4 7         在[4,7]区间的没有
输出
3 1 0 0
当时看了下数据量比较大,2重for的还是算了,但是排序二分的话,这二维还真不知道该怎么排
第三题是cf12D改的
那题是
给你N个女人的三个指标,如果有一个女人的三个指标都比i女人大,那么i女人就自杀,问总共有多少个女人自杀?
然后自己就想成了,for一下然后只要比i都大的人数>=1就+1,然后就输出结果就行了~
然后就不自觉的问了,这一二三维怎么查最快!- -
另外问题四也打错了,应该是求[a,b]的区间,今天试了一下就是hdu1166敌兵布阵(树状数组AC)~，所以现在删除了问题5和6,- -动大手术了！



   

Susake_

第一题的二分出来了,在找到key的前提下继续前移,由于是降序输出的结果就是答案~

1. #include <bits/stdc++.h>
   
2. 
   
3. int a[5] = {5, 3, 3, 2, 1};
   
4. 
   
5. template <class T>
   
6. inline T bfind(T r, T key)
   
7. {
   
8.     T l = 1, m, k, flag = 0;
   
9.     while(l != r)
   
10.     {
    
11.         m = (r + l) / 2;
    
12.         if(a[m] > key) l = m + 1;
    
13.         if(a[m] < key) r = m - 1;
    
14.         if(a[m] == key)
    
15.         {
    
16.             r = m - 1;
    
17.             flag = 1;
    
18.             k = m;
    
19.             if(a[r] != key) break;
    
20.         }
    
21.     }
    
22.     return flag ? k : -1;
    
23. }
    
24. 
    
25. int main(int argc, char *argv[])
    
26. {
    
27.     int key = 1;
    
28.     printf("%d\n", bfind(5, key));
    
29.         return 0;
    
30. }

复制代码

Susake_

第四题开始打错了,现在改成了求区间的值了,正好去试了一下树状数组hdu1166

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <math.h>
   
4. #include <time.h>
   
5. #include <string.h>
   
6. #include <iostream>
   
7. #include <vector>
   
8. #include <list>
   
9. #include <stack>
   
10. #include <queue>
    
11. #include <map>
    
12. #include <set>
    
13. #include <algorithm>
    
14. 
    
15. typedef short int int16;///32767
    
16. typedef int int32;///2147483647
    
17. typedef long long int64;///9223372036854775807
    
18. const double PI=acos(-1.0);///3.141593
    
19. const long long MOD=(long long)1E9+7LL;///1000000007
    
20. int Fibonacci[100]={0,1};///
    
21. int Prime[100];///
    
22. int Caltan[100];///
    
23. template <class T> T Susake_pow(T a,T b)///pow
    
24. {T res;if(b==0) return 1;else while((b&1)==0){b>>=1;a*=a;}res=a;b>>=1;while(b!=0){a*=a;if((b&1)!=0)res*=a;b>>=1;}return res;}
    
25. template<class T> inline T gcd(T a,T b)///gcd
    
26. {if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
    
27. template<class T> inline T lcm(T a,T b)///lcm
    
28. {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
    
29. template<class T> inline char *Susake_nsystem(T n)///itoa(26)
    
30. {T t=0,i;char *s,*p;s=(char *)malloc(sizeof(char)*1000);p=(char *)malloc(sizeof(char)*1000);
    
31. while(n){s[t]=n%26+64;if(s[t]==64){s[t]+=26;n-=26;}t++;n/=26;}s[t]='\0';for(i = 0; i < t; i++)p[i]=s[t-1-i];p[i]='\0';free(s);return p;}
    
32. int Susake_system(char *s)///atoi(26)
    
33. {int len=strlen(s),i,sum=0;char p[1000];for(i=0;i<len;i++)p[i]=s[len-1-i]-64;for(i=0;i<len;i++)sum+=p[i]*Susake_pow(26,i);return sum;}
    
34. int isdigit(int c);int islower(int c);int isupper(int c);
    
35. int tolower(int c);int toupper(int c);
    
36. ///union_find
    
37. int fa[1];
    
38. template <class T> inline T union_find(T x)
    
39. {return fa[x] == x ? x : fa[x] = union_find(fa[x]);}
    
40. ///tree array
    
41. int t_a[200001], t_c[200001];
    
42. int t_n;
    
43. template <class T> inline T lowbit(T x){return x&(-x);}
    
44. void update(int p,int x){while(p<=t_n){t_c[p]+=x;p+=lowbit(p);}}
    
45. template <class T> inline T sum(T p){T s=0;while(p>0){s+=t_c[p];p-=lowbit(p);}return s;}
    
46. 
    
47. int main(int argc, char *argv[])
    
48. {
    
49.     int t;
    
50.     scanf("%d", &t);
    
51.     char s[100];
    
52.     for(int z = 1; z <= t; z++)
    
53.     {
    
54.         memset(t_a, 0, sizeof(t_a));
    
55.         memset(t_c, 0, sizeof(t_c));
    
56.         scanf("%d", &t_n);
    
57.         for(int i = 1; i <= t_n; i++)
    
58.         {
    
59.             t_a[i] += 0;
    
60.             update(i, 0);
    
61.         }
    
62.         for(int i = 1; i <= t_n; i++)
    
63.         {
    
64.             int x;
    
65.             scanf("%d%*c", &x);
    
66.             t_a[i] += x;
    
67.             update(i, x);
    
68.         }
    
69.         printf("Case %d:\n", z);
    
70.         while(scanf("%s", s))
    
71.         {
    
72.             if(strcmp(s, "End") == 0) break;
    
73.             if(strcmp(s, "Add") == 0)
    
74.             {
    
75.                 int j, k;
    
76.                 scanf("%d%d", &j, &k);
    
77.                 t_a[j] += k;
    
78.                 update(j, k);
    
79.             }
    
80.             if(strcmp(s, "Sub") == 0)
    
81.             {
    
82.                 int j, k;
    
83.                 scanf("%d%d", &j, &k);
    
84.                 t_a[j] -= k;
    
85.                 update(j, -k);
    
86.             }
    
87.             if(strcmp(s, "Query") == 0)
    
88.             {
    
89.                 int j, k;
    
90.                 scanf("%d%d", &j, &k);
    
91.                 printf("%d\n", sum(k) - sum(j - 1));
    
92.             }
    
93.         }
    
94.         getchar();
    
95.     }
    
96.     return 0;
    
97. }
    

复制代码

ID好难

回复 7# Susake_

很显然二分写的不够好。 用线段树也可以解决这个问题吧，如果是动态插入查询，二分就不行了。