7

Second My Problem First

Time Limit: 12000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1673    Accepted Submission(s): 634

Problem Description

Give you three integers n, A and B.
Then we define S_i = Aⁱ mod B and T_i = Min{ S_k | i-A <= k <= i, k >= 1}
Your task is to calculate the product of T_i (1 <= i <= n) mod B.

 

Input

Each line will contain three integers n(1 <= n <= 10⁷),A and B(1 <= A, B <= 2³¹-1).
Process to end of file.

 

Output

For each case, output the answer in a single line.

 

Sample Input

1 2 3

2 3 4

3 4 5

4 5 6

5 6 7

 

Sample Output

2

3

4

5

6

思路：单调队列；

就是找区间的最小值，而且区间长度固定，那么用单调队列维护一下就可以了，复杂度O（n）；

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
#include<stack>
#include<set>
#include<queue>
#include<deque>
using namespace std;
typedef long long LL;
using namespace std;
int ans[10000005];
int ic[10000005];
int main(void)
{
        LL n,a,b;
        while(scanf("%lld %lld %lld",&n,&a,&b)!=EOF)
        {
                int i,j;
                LL ask = 1;
                ans[1] = a%b;
                int l = 1,r = 0;
                for(i = 2; i <= n; i++)
                        ans[i] =(int) ((LL)ans[i-1]*(LL)a%b);
                for(i = 1; i <= n; i++)
                {
                        int x = max(i-a,(LL)1);
                        if(l > r)
                        {
                                ic[++r] = i;
                                ask =((LL)ask*(LL)ans[i]%b);
                        }
                        else
                        {
                                while(l <= r)
                                {
                                        int c = ic[r];
                                        if(ans[i] <= ans[c])
                                        {
                                                r--;
                                        }
                                        else
                                        {
                                                ic[++r] = i;
                                                break;
                                        }
                                        if(l > r)
                                        {
                                                ic[++r] = i;
                                                break;
                                        }
                                }
                                while(ic[l]<x)
                                {
                                        l++;
                                }
                                int  maxx =ic[l];
                                ask = ask*(LL)ans[maxx]%b;
                        }
                }
                printf("%lld
",ask);
        }
        return 0;
}

Largest Rectangle in a Histogram

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 19670		Accepted: 6360

Description

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1<=n<=100000. Then follow n integers h₁,...,h_n, where 0<=h_i<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Sample Output

8
4000

Hint

Huge input, scanf is recommended.

思路：单调栈；

单调栈模板题，找每个点能扩展到的最大区间，那么这个面积就是ans[i]*(R[i]-L[i]+1),然后更新最大值。

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<queue>
#include<deque>
#include<stack>
#include<math.h>
using namespace std;
int ans[100002];
int R[100002];
int L[100002];
stack<int>stac;
typedef long long LL;
int main(void)
{
        int n;
        int i,j;
        while(scanf("%d",&n),n!=0)
        {
                for(i = 1; i <= n; i++)
                        scanf("%d",&ans[i]);
                while(!stac.empty())
                    stac.pop();
                LL maxx  = 0;
                for(i = 1; i <= n;i++)
                {
                      if(stac.empty())
                      {
                          L[i] = 1;
                          stac.push(i);
                      }
                      else
                      {
                          while(!stac.empty())
                          {
                              int x = stac.top();
                              if(ans[x] > ans[i])
                              {
                                  R[x] = i-1;
                                  stac.pop();
                              }
                              else
                              {
                                  L[i] = x+1;
                                  stac.push(i);
                                  break;
                              }
                          }
                          if(stac.empty())
                          {
                              L[i] = 1;
                              stac.push(i);
                          }
                      }
                }
                while(!stac.empty())
                {
                     int x = stac.top();
                     R[x] = n;
                     stac.pop();
                }
                for(i = 1;i <= n;i++)
                {
                    maxx = max(maxx,(LL)(R[i]-L[i]+1)*(LL)(ans[i]));
                }
                printf("%lld
",maxx);
        }
        return 0;
}

B. Queue

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There are n walruses standing in a queue in an airport. They are numbered starting from the queue's tail: the 1-st walrus stands at the end of the queue and the n-th walrus stands at the beginning of the queue. The i-th walrus has the age equal to a_i.

The i-th walrus becomes displeased if there's a younger walrus standing in front of him, that is, if exists such j (i < j), that a_i > a_j. The displeasure of the i-th walrus is equal to the number of walruses between him and the furthest walrus ahead of him, which is younger than the i-th one. That is, the further that young walrus stands from him, the stronger the displeasure is.

The airport manager asked you to count for each of n walruses in the queue his displeasure.

Input

The first line contains an integer n (2 ≤ n ≤ 10⁵) — the number of walruses in the queue. The second line contains integers a_i (1 ≤ a_i ≤ 10⁹).

Note that some walruses can have the same age but for the displeasure to emerge the walrus that is closer to the head of the queue needs to be strictly younger than the other one.

Output

Print n numbers: if the i-th walrus is pleased with everything, print "-1" (without the quotes). Otherwise, print the i-th walrus's displeasure: the number of other walruses that stand between him and the furthest from him younger walrus.

Examples

Input

6
10 8 5 3 50 45

Output

2 1 0 -1 0 -1 

Input

7
10 4 6 3 2 8 15

Output

4 2 1 0 -1 -1 -1 

Input

5
10 3 1 10 11

Output

1 0 -1 -1 -1 
思路：二分;
题目意思就是找最右边比当前数小的那数与当前数之间隔了多少个数；我们从右边开始，先维护一个单调的队列，当当前的数小于队尾的数的时候
加入队尾，否则不加，这样队列是递减的。这样，如果当前的数大于队尾的数，那么这个数是无用的，因为还未加入的数，要找比他小的肯定是找那个小的数。
那么这样我们就可以二分找答案了。复杂度N*log(N)；

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<queue>
#include<deque>
#include<stack>
#include<math.h>
using namespace std;
int ans[100005];
int bns[100005];
int id[100005];
int ask[100005];
int main(void)
{
        int n;
        while(scanf("%d",&n)!=EOF)
        {
                int i,j;
                for(i = 0; i < n; i++)
                {
                        scanf("%d",&ans[i]);
                }
                int head = 0;
                for(i = n-1; i >= 0; i--)
                {
                        if(head == 0)
                        {
                                bns[head] = ans[i];
                                id[head] = i;
                                head++;
                        }
                        else
                        {
                                if(bns[head-1]>ans[i])
                                {
                                        bns[head] = ans[i];
                                        id[head] = i;
                                        head++;
                                }
                        }
                        int l = 0;
                        int r = head-1;
                        int ic = -1;
                        while(l<=r)
                        {
                                int mid = (l+r)/2;
                                if(bns[mid] < ans[i])
                                {
                                        ic = mid;
                                        r = mid-1;
                                }
                                else
                                {
                                        l = mid+1;
                                }
                        }
                        if(ic == -1)
                                ask[i] = -1;
                        else ask[i] = id[ic]-i-1;
                }
                printf("%d",ask[0]);
                for(i = 1; i < n; i++)
                {
                        printf(" %d",ask[i]);
                }
        }
        return 0;
}

 Problem 1894 志愿者选拔 

Problem 1894 志愿者选拔

Accept: 1895    Submit: 5852
Time Limit: 1500 mSec    Memory Limit : 32768 KB

Problem Description

世博会马上就要开幕了，福州大学组织了一次志愿者选拔活动。
参加志愿者选拔的同学们排队接受面试官们的面试。参加面试的同学们按照先来先面试并且先结束的原则接受面试官们的考查。
面试中每个人的人品是主要考查对象之一。（提高人品的方法有扶老奶奶过街，不闯红灯等）
作为主面试官的John想知道当前正在接受面试的同学队伍中人品值最高的是多少。于是他请你帮忙编写一个程序来计算。

Input

输入数据第一行为一整数T，表示有T组输入数据。每组数据第一行为”START”，表示面试开始
接下来的数据中有三种情况：

	输入	含义
1	C NAME RP_VALUE	名字为NAME的人品值为RP_VALUE的同学加入面试队伍。(名字长度不大于5，0 <= RP_VALUE <= 1,000,000,000)
2	G	排在面试队伍最前面的同学面试结束离开考场。
3	Q	主面试官John想知道当前正在接受面试的队伍中人品最高的值是多少。

最后一行为”END”，表示所有的面试结束，面试的同学们可以依次离开了。
所有参加面试的同学总人数不超过1,000,000

Output

对于每个询问Q,输出当前正在接受面试的队伍中人品最高的值,如果当前没有人正在接受面试则输出-1。

Sample Input

2 START C Tiny 1000000000 C Lina 0 Q G Q END START Q C ccQ 200 C cxw 100 Q G Q C wzc 500 Q END

Sample Output

1000000000 0 -1 200 100 500

思路：单调队列；

维护一个递减的单调队列，每次查询即可；

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<queue>
#include<deque>
#include<stack>
#include<math.h>
using namespace std;
typedef long long LL;
char str[1000];
char a[10000];
int cnt[1000005];
int quq[1000006];
int main(void)
{
        int n;
        scanf("%d",&n);
        while(n--)
        {
                int cn = 0;
                int hh = 0;
                int head = 1;
                int rail = 0;
                while(scanf("%s",str),str[0]!='E'&&str[1]!='N'&&str[2]!='D')
                {
                        if(str[0]=='C')
                        {
                                scanf("%s",a);
                                scanf("%d",&cnt[cn]);
                                //printf("%d
",cnt[cn]);
                                if(head > rail)
                                {
                                        quq[++rail] = cn;
                                }
                                else
                                {
                                        int x = cnt[quq[rail]];
                                        while(x <= cnt[cn])
                                        {
                                                rail--;
                                                if(rail<head)
                                                        break;
                                                x = cnt[quq[rail]];
                                        }
                                        quq[++rail] = cn;
                                }
                                cn++;
                        }
                        else if(str[0]=='G')
                        {
                                if(rail  >= head)
                                {
                                        int x  = quq[head];
                                        //printf("%d %d
",x,hh);
                                        if(x == hh)
                                        {
                                                head++;
                                        }
                                        hh++;
                                }
                        }
                        else if(str[0]=='Q')
                        {   if(head>rail)printf("-1
");
                            else printf("%d
",cnt[quq[head]]);
                        }
                }
        }
        return 0;
}