찾기 길이

Question

가 0으로 구성된 크기 n의 문자열을 감안할 때 및/또는 1s.you이 K 쿼리를 수행 할 필요가 가능한 쿼리의 이 종류가 조회 .

1. "1"(따옴표 제외) : 가장 긴 부분 문자열의 인쇄 길이는 모두 '1'입니다.
2. "2 X"(따옴표 제외) : 여기서 X는 1에서 n 사이의 정수입니다.이 쿼리에서 X 번째 위치의 문자를 '1'로 변경합니다 (i 번째 위치의 문자가 이미 ' 1 ')

입력 형식 : 입력

• 첫 행, n은 문자열 길이이며, k는 검색어의 개수 N 및 K를 함유한다.
• 다음 줄에는 길이 n의 0 및/또는 1 문자열이 포함됩니다.
• 다음 k 줄마다 각각 하나의 유형 (예 : 1 또는 2)의 검색어가 포함되어 있습니다.

출력 형식 : 형식 1의 각 쿼리에 대해 하위 배열 의 최대 크기를 모두 1로 새 줄에 인쇄하십시오.

 
    Example Input:      Example Output: 
    5 7         0 
    00000         1 
    1          1 
    2 3         3 
    1          
    2 5 
    1 
    2 4 
    1 

내 솔루션 : O (케이 * n)도 (유형 1의 쿼리 대부분의 경우)

if(type==1){ 
     int count=0, ans=0; 
     for(int i=0;i<str.size();i++){ //longest len substring 
      if(str[i]=='1'){ 
       count++; 
      }else{ 
       ans=max(ans,count); 
       count=0; 
      } 
     } 

     printf("%d\n",ans); 
}else{ 
     int xth; 
     scanf("%d",&xth); 
     str[xth-1]='1'; //update 
} 

내가 '유형 1'에 관해서는, 효율적인 솔루션을 알아낼 수 아니다 쿼리 할 수있는 유일한 솔루션은 매번 문자열을 반복하고 모든 "1"의 연속적으로 "count"변수를 유지하고 마지막으로 "ans"변수를 i 번째 str이 '0'이 될 때 업데이트하는 것입니다.

세그먼트 트리를 사용할 생각이지만 어떻게해야할지 모르겠다. 필요에 따라 좋은 솔루션은 O (k * log (n))이어야합니다 (log (n) 시간에 "type1"쿼리 수행)

Answer 1

이것은 각각 숫자가 빈 세트로 시작하는 Disjoint sets datastructure을 사용하여 해결할 수 있습니다.

인덱스 i의 "0"을 "0"으로 전환 할 때. item[i-1] == 1을 확인하십시오. 그렇다면 {i} 세트를 i-1이 포함 된 세트로 결합하십시오. item[i+1]과 유사합니다.

"sets"연결을 끊지 않으므로 새 세트를 계산할 때 "가장 긴 하위 문자열"을 캐시 할 수 있습니다 (방금 작성한 새 하위 세트가 이제 가장 길어 졌는지 확인하고 그렇지 않은 경우 관련 길이 저장)

용액의 시간 복잡도는 "2"유형 동작은 "1"유형 동작 O(1) 및 O(alpha(n))이다 (alpha:N->N는 sublogarithmic 인 역 애커, 임).

k 쿼리에 대해 총 O(k*alpha(n))의 최악의 성능을 얻을 수 있습니다.

따라서, 귀하의 예를 들어 : 여기에 자신의 설명에 따라

5 7 
Create 5 sets: {1} {2} {3} {4} {5} 
00000 
1 
Nothing cached, answer is 0 
2 3 
2 and 4 are zeros, so don't connect with anything. Cache biggest length 1 ({3}) 
1 
1 is cached 
2 5 
Flip 5. Don't connect with anything. 
1 
1 is cached 
2 4 
Flip 4. Join({3},{4}) Since both are 1. Join({3,4},{5}) similarly. Cache 3 (since it's the new size of the set contianing 4 is bigger than 1). 
1 
3 is cached. 

Answer 2

절대적으로 완벽한 @amit는 C++ 여기에 구현
순위 당신이 O에 검색어 1을 반환 할 수 있도록 최대 제정 일의의를 유지하기위한 것입니다 (1) 시간은 업데이트하는 동안 SO1이 항상 최대 1을가집니다.

#include <bits/stdc++.h> 
using namespace std; 
typedef struct subset 
{ 
    int parent; 
    int rank; 
}subset; 
int find(subset subsets[], int i) 
{ 
    if (subsets[i].parent != i) 
     subsets[i].parent = find(subsets, subsets[i].parent); 
    return subsets[i].parent; 
} 
void Union(subset subsets[], int x, int y) 
{ 
    int xroot = find(subsets, x); 
    int yroot = find(subsets, y); 
    if(subsets[xroot].rank < subsets[yroot].rank) 
    { 
     subsets[xroot].parent = yroot; 
     subsets[yroot].rank += subsets[xroot].rank; 
    } 
    else if (subsets[xroot].rank > subsets[yroot].rank) 
    { 
     subsets[yroot].parent = xroot; 
     subsets[xroot].rank += subsets[yroot].rank; 
    } 
    else 
    { 
     subsets[yroot].parent = xroot; 
     subsets[xroot].rank+=subsets[yroot].rank; 
    } 
} 
int main() 
{ 
    ios::sync_with_stdio(false); 
    cin.tie(0); 
    cout.tie(0); 
    int n,k,i,q,t,sol=0; 
    cin >> n >> k; 
    string s; 
    cin >> s; 
    cin.ignore(); 
    subset subsets[n]; 
    for(i=0;i<n;i++) 
    { 
     subsets[i].parent = i; 
     subsets[i].rank = 0; 
     if(s[i]=='1') 
     { 
      subsets[i].rank = 1; 
     } 
    } 
    for(t=0;t<n;t++) 
    { 
     if(s[t] == '1' && t!=0 && t!=n-1) 
     { 
      if(s[t-1] == '1') 
      { 
       int x = find(subsets,t-1); 
       int y = find(subsets,t); 
       if(x!=y) 
       { 

        Union(subsets,t-1,t); 
        sol = max(sol,max(subsets[x].rank,subsets[y].rank)); 
        sol = max(sol,subsets[t].rank); 
       } 
      } 
      if(s[t+1] == '1') 
      { 
       int x = find(subsets,t+1); 
       int y = find(subsets,t); 
       if(x!=y) 
       { 
        Union(subsets,t+1,t); 
        sol = max(sol,max(subsets[x].rank,subsets[y].rank)); 
        sol = max(sol,subsets[t].rank); 
       } 
      } 
     } 
     if(s[t] == '1' && t==0) 
     { 
      if(s[t+1] == '1') 
      { 
       int x = find(subsets,t+1); 
       int y = find(subsets,t); 
       if(x!=y) 
       { 

        Union(subsets,t+1,t); 
        sol = max(sol,max(subsets[x].rank,subsets[y].rank)); 
        sol = max(sol,subsets[t].rank); 
       } 
      } 
     } 
     if(s[t] == '1' && t==n-1) 
     { 
      if(s[t-1] == '1') 
      { 
       int x = find(subsets,t-1); 
       int y = find(subsets,t); 
       if(x!=y) 
       { 

        Union(subsets,t-1,t); 
        sol = max(sol,max(subsets[x].rank,subsets[y].rank)); 
        sol = max(sol,subsets[t].rank); 
       } 
      } 
     } 
     sol = max(sol,subsets[t].rank); 
    } 
    for(i=0;i<k;i++) 
    { 
     cin >> q; 
     if(q==1) 
     { 
      cout << sol << endl; 
     } 
     else 
     { 
      cin >> t; 
      t--; 
      if(s[t] == '0' && t!=0 && t!=n-1) 
      { 
       s[t] = '1'; 
       subsets[t].rank = 1; 
       if(s[t-1] == '1') 
       { 
        int x = find(subsets,t-1); 
        int y = find(subsets,t); 
        if(x!=y) 
        { 

         Union(subsets,t-1,t); 
         sol = max(sol,max(subsets[x].rank,subsets[y].rank)); 
         sol = max(sol,subsets[t].rank); 
        } 
       } 
       if(s[t+1] == '1') 
       { 
        int x = find(subsets,t+1); 
        int y = find(subsets,t); 
        if(x!=y) 
        { 

         Union(subsets,t+1,t); 
         sol = max(sol,max(subsets[x].rank,subsets[y].rank)); 
         sol = max(sol,subsets[t].rank); 
        } 
        //Union(subsets,t+1,t); 
       } 
      } 
      if(s[t] == '0' && t==0) 
      { 
       s[t] = '1'; 
       subsets[t].rank = 1; 
       if(s[t+1] == '1') 
       { 
        int x = find(subsets,t+1); 
        int y = find(subsets,t); 
        if(x!=y) 
        { 
         Union(subsets,t+1,t); 
         sol = max(sol,max(subsets[x].rank,subsets[y].rank)); 
         sol = max(sol,subsets[t].rank); 
        } 
       } 
      } 
      if(s[t] == '0' && t==n-1) 
      { 
       s[t] = '1'; 
       subsets[t].rank = 1; 
       if(s[t-1] == '1') 
       { 
        int x = find(subsets,t-1); 
        int y = find(subsets,t); 
        if(x!=y) 
        { 
         Union(subsets,t-1,t); 
         sol = max(sol,max(subsets[x].rank,subsets[y].rank)); 
         sol = max(sol,subsets[t].rank); 
        } 
       } 
      } 
      sol = max(sol,subsets[t].rank); 
     } 
    } 
}