HDU 4339 Query 2012多校リーグ第4戦I題(setまたは線分樹、以下set解法)
Query
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2074 Accepted Submission(s): 713
Problem Description
You are given two strings s1[0..l1], s2[0..l2] and Q - number of queries.
Your task is to answer next queries:
1) 1 a i c - you should set i-th character in a-th string to c;
2) 2 i - you should output the greatest j such that for all k (i<=k and k
Input
The first line contains T - number of test cases (T<=25).
Next T blocks contain each test.
The first line of test contains s1.
The second line of test contains s2.
The third line of test contains Q.
Next Q lines of test contain each query:
1) 1 a i c (a is 1 or 2, 0<=i, i 2) 2 i (0<=i, iAll characters in strings are from 'a'..'z' (lowercase latin letters).
Q <= 100000.
l1, l2 <= 1000000.
Output
For each test output "Case t:"in a single line, where t is number of test (numbered from 1 to T).
Then for each query "2 i"output in single line one integer j.
Sample Input
Sample Output
テーマ:
2つの列をあげます.2つの操作があります.1つ目はクエリーで、出力がiから何個連続して等しいかを示します.2つ目は、ある一連の位置の値を変更することです.
问题を解く考え方:当时、博博博と大きな力を费やしてこの问题をやって、ある値を変えて、后の更新は必要ありません.前のは一歩一歩前に判断しなければなりません.等しくない时まで、时間は10 sをあげました.その时、试してみる気持ちを持って行きました.後でセグメントツリーであることが証明されました.夜、男神は私たちにこの問題のset解法を話してくれましたが、この方法を考えるのはそんなに簡単ではありません.試合の時にここまで抽象化できるのはすごいので、もっと考えなければなりません.毎回iから等しくない距離をクエリするので,等しくない位置をsetにすべて存在させる.でも時間は2609 msしかありません...
タイトルアドレス:Query
ACコード:
ジジが中のeraseの問題を探してくれてありがとう.eraseはポインタを削除したり、値を削除したりすることができます.しかし、aより大きい値が見つからないと、上のitはend()になり、end()を削除することはできません.そうしないと、後で本当にaより大きい値が見つかりません.end()を削除します.木にコンパイルエラーがありますが、削除しないほうがいいです.そして試したばかりで、end()の対応する値は0.では、どのようにaより大きいのか、不思議ですね.もちろんend()は大きいと理解できますが、あまり見つからないときだけitがend()になります.
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2074 Accepted Submission(s): 713
Problem Description
You are given two strings s1[0..l1], s2[0..l2] and Q - number of queries.
Your task is to answer next queries:
1) 1 a i c - you should set i-th character in a-th string to c;
2) 2 i - you should output the greatest j such that for all k (i<=k and k
Input
The first line contains T - number of test cases (T<=25).
Next T blocks contain each test.
The first line of test contains s1.
The second line of test contains s2.
The third line of test contains Q.
Next Q lines of test contain each query:
1) 1 a i c (a is 1 or 2, 0<=i, i
Q <= 100000.
l1, l2 <= 1000000.
Output
For each test output "Case t:"in a single line, where t is number of test (numbered from 1 to T).
Then for each query "2 i"output in single line one integer j.
Sample Input
1
aaabba
aabbaa
7
2 0
2 1
2 2
2 3
1 1 2 b
2 0
2 3
Sample Output
Case 1:
2
1
0
1
4
1
テーマ:
2つの列をあげます.2つの操作があります.1つ目はクエリーで、出力がiから何個連続して等しいかを示します.2つ目は、ある一連の位置の値を変更することです.
问题を解く考え方:当时、博博博と大きな力を费やしてこの问题をやって、ある値を変えて、后の更新は必要ありません.前のは一歩一歩前に判断しなければなりません.等しくない时まで、时間は10 sをあげました.その时、试してみる気持ちを持って行きました.後でセグメントツリーであることが証明されました.夜、男神は私たちにこの問題のset解法を話してくれましたが、この方法を考えるのはそんなに簡単ではありません.試合の時にここまで抽象化できるのはすごいので、もっと考えなければなりません.毎回iから等しくない距離をクエリするので,等しくない位置をsetにすべて存在させる.でも時間は2609 msしかありません...
タイトルアドレス:Query
ACコード:
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<set>
using namespace std;
char s1[1000005],s2[1000005];
int main()
{
set<int> mq;
set<int>::iterator it; //
int T,cas,n,q,a,i,p;
char c,kong;
scanf("%d",&T);
for(cas=1;cas<=T;cas++)
{
printf("Case %d:
",cas);
mq.clear(); //
scanf("%s%s",s1,s2);
int len1=strlen(s1),len2=strlen(s2);
int len=len1<len2?len1:len2;
for(i=0;i<len;i++)
if(s1[i]!=s2[i])
mq.insert(i); //
mq.insert(i); // ,
scanf("%d",&n);
while(n--)
{
scanf("%d",&q);
if(q==2) //
{
int ans;
scanf("%d",&a);
ans=*mq.lower_bound(a);
printf("%d
",ans-a);
}
else if(q==1) //
{
scanf("%d%d%c%c",&p,&a,&kong,&c); //
//cout<<p<<" "<<a<<" "<<c<<endl;
if(p==1) //
{
if(s1[a]==s2[a]&&c!=s2[a])
mq.insert(a);
else if(s1[a]!=s2[a]&&c==s2[a])
{
//s1 6 s2 3 . s1 5
// end end
/*it=mq.lower_bound(a);
if(it!=mq.end())
mq.erase(it);*/ //
mq.erase(a);
}
s1[a]=c;
}
else //
{
if(s1[a]==s2[a]&&c!=s1[a])
mq.insert(a);
else if(s1[a]!=s2[a]&&c==s1[a])
mq.erase(a);
s2[a]=c;
}
}
}
}
return 0;
}
ジジが中のeraseの問題を探してくれてありがとう.eraseはポインタを削除したり、値を削除したりすることができます.しかし、aより大きい値が見つからないと、上のitはend()になり、end()を削除することはできません.そうしないと、後で本当にaより大きい値が見つかりません.end()を削除します.木にコンパイルエラーがありますが、削除しないほうがいいです.そして試したばかりで、end()の対応する値は0.では、どのようにaより大きいのか、不思議ですね.もちろんend()は大きいと理解できますが、あまり見つからないときだけitがend()になります.