Query

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2595 Accepted Submission(s): 860

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, i All 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

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

Source 2012 Multi-University Training Contest 4
解题思路：用保存字符不同的位置，修改的话直接改，查的话用lower_bound，注意要把字符串长度len也添加进去，这是为了避免字符串全部相等的情况

#include 
     
      
#include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #define Maxn 1000005 using namespace std; char str1[Maxn],str2[Maxn]; int main() { int t,ncase=1,q,a,c,b; char ch; set
           
             s; //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&t); while(t--) { s.clear(); set
            
             ::iterator it; scanf("%s%s",str1,str2); scanf("%d",&q); int len=strlen(str1); for(int i=0;i

HDU 4339 Query

Query