[CF][差分标记]-白红宇

[CF][差分标记]

阅读量：5170 次

发布时间：2019-06-13

本文共 5806 字，大约阅读时间需要 19 分钟。

所有元素初始值为0才能这么做。

①l--r全加1

a[l]++;

a[r+1]--;

求一遍前缀和为元素本身。

求两遍前缀和为元素前缀和。

②l--r从1加到l-r+1

a[l]++;

a[r+1]-=l-r+2;

a[r+2]+=l-r+1;

求两遍前缀和为元素本身。

求三遍前缀和为元素前缀和。

因为更新时复杂度是o(1)所以复杂度为求前缀和时的o(N)。

例题一：Karen and Coffee

Description

To stay woke and attentive during classes, Karen needs some coffee!

Karen, a coffee aficionado, wants to know the optimal temperature for brewing the perfect cup of coffee. Indeed, she has spent some time reading several recipe books, including the universally acclaimed "The Art of the Covfefe".

She knows n coffee recipes. The i-th recipe suggests that coffee should be brewed between liand ri degrees, inclusive, to achieve the optimal taste.

Karen thinks that a temperature is admissible if at least k recipes recommend it.

Karen has a rather fickle mind, and so she asks q questions. In each question, given that she only wants to prepare coffee with a temperature between a and b, inclusive, can you tell her how many admissible integer temperatures fall within the range?

Input

The first line of input contains three integers, n, k (1 ≤ k ≤ n ≤ 200000), and q(1 ≤ q ≤ 200000), the number of recipes, the minimum number of recipes a certain temperature must be recommended by to be admissible, and the number of questions Karen has, respectively.

The next n lines describe the recipes. Specifically, the i-th line among these contains two integers li and ri (1 ≤ li ≤ ri ≤ 200000), describing that the i-th recipe suggests that the coffee be brewed between li and ri degrees, inclusive.

The next q lines describe the questions. Each of these lines contains a and b, (1 ≤ a ≤ b ≤ 200000), describing that she wants to know the number of admissible integer temperatures between a and b degrees, inclusive.

Output

For each question, output a single integer on a line by itself, the number of admissible integer temperatures between a and b degrees, inclusive.

Examples

Input

3 2 4

91 94

92 97

97 99

92 94

93 97

95 96

90 100

Output

正确解法：

题目意思是说，给定n个区间，再给个q个区间。

求每个区间内的数在上面区间内部至少有k次的个数。

看例子，就是 92-94 中有三个数92 93 94，我们发现这三个数在上面3个区间内都出现了两次 >=k

于是这三个数都符合条件，输出3.

就是给区间，然后区间内的数都+1，再给区间，找区间内的数大于K的个数。

刚刚学了差分标记嘛，当+1的时候就会很快.

当输入区间后，每次重新赋值为0，然后查找，再输出就有点慢。

因为K是不变的，我们就可以把大于等于K的值变为1，小于K的值变为0，求前缀和就ok

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
           6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 using namespace std;11 int n, k, q,aa,bb;12 int f[201000];13 int main()14 {15 scanf("%d %d %d",&n,&k,&q);16 while (n--)17 {18 scanf("%d %d",&aa,&bb);19 f[aa]++;20 f[bb + 1]--;21 }22 for (int i = 1; i <= 200000; i++)23 f[i] += f[i - 1];24 for (int i = 1; i <= 200000; i++)25 {26 if (f[i] >= k) f[i] = 1;27 else f[i] = 0;28 }29 for (int i = 1; i <= 200000; i++)30 f[i] += f[i - 1];31 while (q--)32 {33 scanf("%d %d",&aa,&bb);34 printf("%d\n",f[bb]-f[aa-1]);35 }36 return 0;37 }

View Code

例题二：The Festive Evening

Description

It's the end of July – the time when a festive evening is held at Jelly Castle! Guests from all over the kingdom gather here to discuss new trends in the world of confectionery. Yet some of the things discussed here are not supposed to be disclosed to the general public: the information can cause discord in the kingdom of Sweetland in case it turns out to reach the wrong hands. So it's a necessity to not let any uninvited guests in.

There are 26 entrances in Jelly Castle, enumerated with uppercase English letters from A to Z. Because of security measures, each guest is known to be assigned an entrance he should enter the castle through. The door of each entrance is opened right before the first guest's arrival and closed right after the arrival of the last guest that should enter the castle through this entrance. No two guests can enter the castle simultaneously.

For an entrance to be protected from possible intrusion, a candy guard should be assigned to it. There are k such guards in the castle, so if there are more than k opened doors, one of them is going to be left unguarded! Notice that a guard can't leave his post until the door he is assigned to is closed.

Slastyona had a suspicion that there could be uninvited guests at the evening. She knows the order in which the invited guests entered the castle, and wants you to help her check whether there was a moment when more than k doors were opened.

Input

Two integers are given in the first string: the number of guests n and the number of guards k(1 ≤ n ≤ 106, 1 ≤ k ≤ 26).

In the second string, n uppercase English letters s1s2... sn are given, where si is the entrance used by the i-th guest.

Output

Output «YES» if at least one door was unguarded during some time, and «NO» otherwise.

You can output each letter in arbitrary case (upper or lower).

Examples

Input

5 1

ABABB

Output

YES

正确解法：

每一个字母是一个门，门在第一个人来的时候开着，只有在最后一个进入这个门的时候关着，在开着的期间必须有守卫看守，现在有K个守卫，是否会缺少守卫？

当守卫这个门关掉之后，这个守卫可以去其他的门看守。

就是找第一个客人和最后一个客人，在这中间门都要开着。可以利用差分标记。

最后求一下前缀和，求最大的数就是守卫的个数。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
           6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 using namespace std;11 int n, k;12 int a[30], b[30], f[1001000];13 char s[1001000];14 int main()15 {16 scanf("%d %d", &n, &k);17 getchar();18 gets(s);19 for(int i=n;i>=1;i--)20 s[i]=s[i-1];21 for (int i = 1; i <= n; i++)22 {23 if (a[s[i] - 'A'+1] == 0)24 a[s[i] - 'A'+1] = i;25 b[s[i] - 'A' + 1] = i;26 }27 for (int i = 1; i <= 26; i++)28 {29 f[a[i]]++;30 f[b[i] + 1]--;31 }32 int maxx = 0;33 for (int i = 1; i <= n; i++)34 {35 f[i] += f[i - 1];36 maxx = max(maxx,f[i]);37 }38 if(maxx>k) printf("YES\n");39 else printf("NO\n");40 return 0;41 }