HDU 6406 Taotao Picks Apples(欲張り列挙+最適化+小暴力)
Taotao Picks Apples
Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 338 Accepted Submission(s): 87
Problem Description
There is an apple tree in front of Taotao's house. When autumn comes, n apples on the tree ripen, and Taotao will go to pick these apples. When Taotao picks apples, Taotao scans these apples from the first one to the last one. If the current apple is the first apple, or it is strictly higher than the previously picked one, then Taotao will pick this apple; otherwise, he will not pick. Given the heights of these apples h1,h2,⋯,hn, you are required to answer some independent queries. Each query is two integers p,q, which asks the number of apples Taotao would pick, if the height of the p-th apple were q (instead of hp). Can you answer all these queries?
Input
The first line of input is a single line of integer T (1≤T≤10), the number of test cases. Each test case begins with a line of two integers n,m (1≤n,m≤105), denoting the number of apples and the number of queries. It is then followed by a single line of n integers h1,h2,⋯,hn (1≤hi≤109), denoting the heights of the apples. The next m lines give the queries. Each of these m lines contains two integers p (1≤p≤n) and q (1≤q≤109), as described in the problem statement.
Output
For each query, display the answer in a single line.
Sample Input
1 5 3 1 2 3 4 4 1 5 5 5 2 3
Sample Output
1 5 3
Hint
For the first query, the heights of the apples were 5, 2, 3, 4, 4, so Taotao would only pick the first apple. For the second query, the heights of the apples were 1, 2, 3, 4, 5, so Taotao would pick all these five apples. For the third query, the heights of the apples were 1, 3, 3, 4, 4, so Taotao would pick the first, the second and the fourth apples.
題意:n(n<=1 e 5)個の数を含むシーケンスをあげます.次にm(m<=1 e 5)回修正し、1つの点の値を毎回修正する.
最初はma=-1で、a[1]から、彼より大きいものに出会ったらa[i]になり、cnt++は、修正するたびに元のシーケンスcntがいくらになるかを尋ねた.(各修正は互いに独立している).
考え方:試合の時に暴力+最適化を工夫します..未修正シーケンスの答えシーケンスの数と位置とcntを前処理し、各ノードiを前処理した後に何回交換するか(単調キュースライドウィンドウが逆さまに行われる)、各数a[i]の後に最もその答えシーケンスの数に近い位置を前処理する.次に、各修正の下付きiが元の答えシーケンスにあるかどうかについて議論する.(中には暴力が必要な場合がありますが、データがランダムであれば完全に通過できます.しかも超神入力掛けを付けた後は156 ms、付けないのは500+msです.)デバッグ中に暴力の部分は当然の2点と思っていたので、それからWAは4回、この長記憶性になりました...
コード:
Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 338 Accepted Submission(s): 87
Problem Description
There is an apple tree in front of Taotao's house. When autumn comes, n apples on the tree ripen, and Taotao will go to pick these apples. When Taotao picks apples, Taotao scans these apples from the first one to the last one. If the current apple is the first apple, or it is strictly higher than the previously picked one, then Taotao will pick this apple; otherwise, he will not pick. Given the heights of these apples h1,h2,⋯,hn, you are required to answer some independent queries. Each query is two integers p,q, which asks the number of apples Taotao would pick, if the height of the p-th apple were q (instead of hp). Can you answer all these queries?
Input
The first line of input is a single line of integer T (1≤T≤10), the number of test cases. Each test case begins with a line of two integers n,m (1≤n,m≤105), denoting the number of apples and the number of queries. It is then followed by a single line of n integers h1,h2,⋯,hn (1≤hi≤109), denoting the heights of the apples. The next m lines give the queries. Each of these m lines contains two integers p (1≤p≤n) and q (1≤q≤109), as described in the problem statement.
Output
For each query, display the answer in a single line.
Sample Input
1 5 3 1 2 3 4 4 1 5 5 5 2 3
Sample Output
1 5 3
Hint
For the first query, the heights of the apples were 5, 2, 3, 4, 4, so Taotao would only pick the first apple. For the second query, the heights of the apples were 1, 2, 3, 4, 5, so Taotao would pick all these five apples. For the third query, the heights of the apples were 1, 3, 3, 4, 4, so Taotao would pick the first, the second and the fourth apples.
題意:n(n<=1 e 5)個の数を含むシーケンスをあげます.次にm(m<=1 e 5)回修正し、1つの点の値を毎回修正する.
最初はma=-1で、a[1]から、彼より大きいものに出会ったらa[i]になり、cnt++は、修正するたびに元のシーケンスcntがいくらになるかを尋ねた.(各修正は互いに独立している).
考え方:試合の時に暴力+最適化を工夫します..未修正シーケンスの答えシーケンスの数と位置とcntを前処理し、各ノードiを前処理した後に何回交換するか(単調キュースライドウィンドウが逆さまに行われる)、各数a[i]の後に最もその答えシーケンスの数に近い位置を前処理する.次に、各修正の下付きiが元の答えシーケンスにあるかどうかについて議論する.(中には暴力が必要な場合がありますが、データがランダムであれば完全に通過できます.しかも超神入力掛けを付けた後は156 ms、付けないのは500+msです.)デバッグ中に暴力の部分は当然の2点と思っていたので、それからWAは4回、この長記憶性になりました...
コード:
#include
#define ll long long
using namespace std;
namespace fastIO {
#define BUF_SIZE 100000
//fread -> read
bool IOerror = 0;
inline char nc() {
static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
if(p1 == pend) {
p1 = buf;
pend = buf + fread(buf, 1, BUF_SIZE, stdin);
if(pend == p1) {
IOerror = 1;
return -1;
}
}
return *p1++;
}
inline bool blank(char ch) {
return ch == ' ' || ch == '
' || ch == '\r' || ch == '\t';
}
inline void read(int &x) {
char ch;
while(blank(ch = nc()));
if(IOerror) return;
for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
}
#undef BUF_SIZE
};
using namespace fastIO;
//void read(int &x){scanf("%d",&x);}
const int maxn=100010;
int n,m,k;
int a[maxn],s[maxn],ss[maxn],f;
int c[maxn],r[maxn];
int ans,ct,cnt,tmp,flag;
int qq[maxn],he,ti;
int main()
{
int T,cas=1;
read(T);
while(T--)
{
read(n);read(m);
ans=0; flag=1; f=0;
for(int i=0;ima) {s[f]=i;ss[f++]=a[i];ma=a[i];}
}
a[n+1]=0;ss[f]=1000000009;
int j=f-1;
for(int i=n;i>=1;i--)
{
if(j>0&&i==s[j-1]) j--;
if(s[j]>=i)r[i]=s[j];
else r[i]=n+1;
}
for(int h=1,t=0,i=n;i;i--)
{
while(h<=t&&a[qq[t]]<=a[i])t--;
qq[++t]=i;
c[i]=t;
}
ans=f;
while(m--)
{
int x,y,tmp;
read(x);read(y);
if(r[x]==x)
{
if(y0) ma=ss[k-1];
else ma=-1;
tmp=k;
if(y>ma) {tmp++;ma=y;}
int i;
for(i=s[k]+1;i<=n;i++) if(a[i]>ma) break;//ここは で さなきゃ!!!
tmp+=c[i];
}
else
{
int k=lower_bound(ss,ss+f,a[x])-ss;
tmp=k+1;
k=lower_bound(ss+k+1,ss+f,y+1)-ss;
tmp+=(f-k);
}
}
else
{
int xx=r[x];
if(xx==n+1)
{
if(y>ss[f-1]) tmp=ans+1;
else tmp=ans;
}
else {
int k=lower_bound(ss,ss+f,a[xx])-ss;
if(k>0&&y>ss[k-1]&&y