前缀和

值：a(x),a(x+1),…,a(y)

f(s,t)=a(s)+…+a(t)=T(t)-T(s-1)

其中T(k)=a(x)+…+a(k)

O(t-s+1)的时间复杂度转变为 O(1)

hdu5327

 1 前缀和：求[x,y]区间的总共的值f(x,y)
 2 f(x,y)=T(y)-T(x-1)
 3 其中T(k)=f(begin_index,k)
 4 
 5 hdu 
 6 #include <cstdio>
 7 #include <cstdlib>
 8 #include <cstring>
 9 #include <cmath>
10 #include <list>
11 #include <stack>
12 #include <vector>
13 #include <set>
14 #include <map>
15 #include <queue>
16 #include <algorithm>
17 #include <iostream>
18 using namespace std;
19 
20 long f[100000*6];
21 char s[7];
22 bool v[10];
23 
24 int main()
25 {
26     long x,y,len,i,j,t;
27     f[0]=0;
28     len=0;
29     for (i=1;i<=100000;i++)
30     {
31         itoa(i,s,10);
32         for (j=0;j<10;j++)
33             v[j]=false;
34         len=strlen(s);
35         for (j=0;j<len;j++)
36             if (v[s[j]-48])
37                 break;
38             else
39                 v[s[j]-48]=true;
40         if (j==len)
41             f[i]=f[i-1]+1;
42         else
43             f[i]=f[i-1];
44     }
45     
46     scanf("%ld",&t);
47     while (t--)
48     {
49         scanf("%ld%ld",&x,&y);
50         printf("%ld
",f[y]-f[x-1]);
51     }
52     return 0;
53 }

hdu5480

 1 //满足条件的都是每一行有石头 或 每一列有石头 
 2 //反证法：假设存在x行,y列没石头，则(x,y)坦克无法成立 
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <cmath>
 7 #include <list>
 8 #include <stack>
 9 #include <vector>
10 #include <set>
11 #include <map>
12 #include <queue>
13 #include <algorithm>
14 #include <iostream>
15 using namespace std;
16 
17 long row[100005],col[100005],r[100005],cc[100005];
18 
19 int main()
20 {
21     long t,x,y,k,q,a,b,c,d,i;
22     scanf("%ld",&t);
23     while (t--)
24     {
25         scanf("%ld%ld%ld%ld",&x,&y,&k,&q);
26         for (i=0;i<=x;i++)
27         {
28             row[i]=0;
29             r[i]=0;
30         }
31         for (i=0;i<=y;i++)
32         {
33             col[i]=0;
34             cc[i]=0;
35         }
36         while (k--)
37         {
38             scanf("%ld%ld",&a,&b);
39             r[a]=1;
40             cc[b]=1;
41             //有可能有多个石头在同一个地方
42         }
43         for (i=1;i<=x;i++)
44             row[i]=row[i-1]+r[i];
45         for (i=1;i<=y;i++)
46             col[i]=col[i-1]+cc[i];
47         while (q--)
48         {
49             scanf("%ld%ld%ld%ld",&a,&b,&c,&d);
50             if (row[c]-row[a-1]==c-a+1 || col[d]-col[b-1]==d-b+1)
51                 printf("Yes
");
52             else
53                 printf("No
");
54         }
55     }
56     return 0;
57 }

hdu5700