Data Structure:
Problem Link: QCHEF
My Solution:
Click to See Code
//
// main.cpp
// QCHEF
//
// Created by Matrix.code on 3/14/17.
// Copyright © 2017 Matrix.code. All rights reserved.
//
#include<bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define Long long long
#define Ulong unsigned long long
#define FOR(I,A,B) for(int I = (A); I < (B) ; ++ I)
#define REP(i,n) for( int i=0 ; i < n ; i++ )
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define PI acos(-1.0)
#define EPS 1e-9
#define F first
#define S second
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(x) int x;scanf("%d",&x)
#define in(x) input(x)
#define in2(x,y) input(x), input(y)
#define in3(x,y,z) input(x), input(y),input(z)
#define ins(x) scanf("%s",x)
#define ind(x) scanf("%lf",&x)
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
#define IO ios_base::sync_with_stdio(0);cin.tie(0)
#define READ freopen("/Users/matrixcode/Desktop/in.txt","r",stdin)
#define WRITE freopen("/Users/matrixcode/Desktop/out.txt","w",stdout)
template<class T > void input(T &x){
char c = getchar();x = 0;
for(;(c<48 || c>57);c = getchar());
for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;} } inline long long bigmod(long long p,long long e,long long M){ long long ret = 1; for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
/***************************** END OF TEMPLATE *******************************/
const int N = 1e5+5;
const int RootN = 350;
int n,m,q;
int a[N];
int Beg[RootN] , End[RootN], Id[N] , dp[RootN][N], dp2[RootN][N];
int block;
int main()
{
in3(n,m,q);
REP(i,n) in(a[i]);
block = 2*sqrt(n)+1;
REP(i,n) {
Id[i] = i/block;
if(i%block==0){
Beg[i/block] = i;
End[i/block] = min(n-1, (Id[i]+1)*block-1);
}
}
for(int i = 0;i <= Id[n-1] ; i++ ) {
int Map[N]; ms(Map,-1);
int iM = 0;
for(int j = Beg[i] ; j < n ;j ++ ) { if(Map[a[j]]>=0) {
iM = max(iM, j - Map[a[j]] );
} else Map[a[j]] = j;
dp[i][j] = iM;
}
}
for(int i=0;i<=Id[n-1]; i++ ){ int Map[N]; ms(Map,-1); int iM = 0; for(int j= End[i]; j>= 0; j--) {
if(Map[a[j]]>=0) {
iM = max(iM, Map[a[j]] - j );
} else Map[a[j]] = j;
dp2[i][j] = iM;
}
}
int x,y;
int Map[N]; ms(Map,-1);
while(q--) {
in2(x,y); x--,y--;
if(Id[x]== Id[y]) {
int ans = 0;
for(int i= x;i <=y;i++) { if(Map[a[i]]>=0) {
ans = max(ans, i - Map[a[i]] );
}
else Map[a[i]] = i;
}
for(int i=x;i<=y;i++){
Map[a[i]] = -1;
}
printf("%d\n",ans);
}
else {
int L = (x== Beg[Id[x]]) ? Id[x] : Id[x]+1;
int R = (y== End[Id[y]]) ? Id[y] : Id[y]-1;
int ans = 0;
if(Beg[L] <= y) ans = max(ans, dp[L][y]);
if(x <= End[R]) ans = max(ans, dp2[R][x]);
vector<pair<int,int> > v;
for(int i=x;i<Beg[L];i++)v.push_back(mp(a[i],i));
for(int i=End[R]+1;i<=y;i++)v.push_back(mp(a[i],i)); for(auto a: v) { if(Map[a.F] >= 0) {
ans = max(ans, a.S - Map[a.F]);
}else Map[a.F] = a.S;
}
for(auto a: v) {
Map[a.F] = -1;
}
printf("%d\n",ans);
}
}
return 0;
}
Problem Link: CUBTOWER
My Solution:
Click to See Code
//
// main.cpp
// CUBTOWER
//
// Created by Matrix.code on 3/15/17.
// Copyright © 2017 Matrix.code. All rights reserved.
//
#include<bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define Long long long
#define Ulong unsigned long long
#define FOR(I,A,B) for(int I = (A); I < (B) ; ++ I)
#define REP(i,n) for( int i=0 ; i < n ; i++ )
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define PI acos(-1.0)
#define EPS 1e-9
#define F first
#define S second
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(x) int x;scanf("%d",&x)
#define in(x) input(x)
#define in2(x,y) input(x), input(y)
#define in3(x,y,z) input(x), input(y),input(z)
#define ins(x) scanf("%s",x)
#define ind(x) scanf("%lf",&x)
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
#define IO ios_base::sync_with_stdio(0);cin.tie(0)
#define READ freopen("/Users/matrixcode/Desktop/in.txt","r",stdin)
#define WRITE freopen("/Users/matrixcode/Desktop/out.txt","w",stdout)
template<class T > void input(T &x){
char c = getchar();x = 0;
for(;(c<48 || c>57);c = getchar());
for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}
}
inline long long bigmod(long long p,long long e,long long M){
long long ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
/***************************** END OF TEMPLATE *******************************/
const int N = 2e5+5;
const int RootN= 350;
struct Event{
int type;
int l,r;
int Time;
};
vector<Event> e[N];
int n,m,q;
long long BASE = 37 , mod = 1e9+7;
long long H(char s[])
{
long long h =0;
for(int i=0;s[i];i++) {
h = (BASE * h + s[i]-'a' + 1 ) % mod;
}
return h;
}
long long value[N];
char str[N];
int len[N];
unordered_map<long long,int> Map;
vector<long long> NString[N];
int uniqueLen[N];
int TLen;
long long POW[N];
void append( int idx, char c)
{
int v = c-'a' + 1;
long long pre = NString[idx].size() ? NString[idx].back() : 0;
NString[idx].push_back((v + BASE* pre ) % mod);
int ptr = (int) NString[idx].size()-1;
for(int i=0;i < TLen ;i ++) {
int l = uniqueLen[i];
if(l > ptr + 1) break;
long long o = ((NString[idx][ptr] - POW[l] * (ptr - l>=0 ? NString[idx][ptr-l] : 0)) % mod + mod ) % mod;
if(Map.count(o) && len[Map[o]] == l ) {
e[Map[o]].push_back({0,idx,-1,-1});
}
}
}
int block;
int Beg[RootN] ,End[RootN], Sum1[RootN] , Sum2[RootN], id[N];
int Arr1[N] , Arr2[N];
long long Ans[N];
void update(int idx)
{
Arr1[idx] ++;
Sum1[id[idx]] ++;
if(Arr2[idx] == 0) Arr2[idx]=1 , Sum2[id[idx]] ++;
}
long long Q1(int x,int y)
{
long long ans = 0;
if(id[x]==id[y]) {
for(int i=x;i<=y;i++) {
ans+= Arr1[i];
}
return ans;
}
int L = (x==Beg[id[x]]) ? id[x] : id[x]+1;
int R = (x==End[id[y]]) ? id[y] : id[y]-1;
for(int i=x;i<Beg[L];i++) ans += Arr1[i];
for(int i=y;i>End[R];i--) ans += Arr1[i];
for(int i=L;i<=R;i++) ans += Sum1[i];
return ans;
}
long long Q2(int x,int y)
{
long long ans = 0;
if(id[x]==id[y]) {
for(int i=x;i<=y;i++) {
ans+= Arr2[i];
}
return ans;
}
int L = (x==Beg[id[x]]) ? id[x] : id[x]+1;
int R = (x==End[id[y]]) ? id[y] : id[y]-1;
for(int i=x;i<Beg[L];i++) ans += Arr2[i];
for(int i=y;i>End[R];i--) ans += Arr2[i];
for(int i=L;i<=R;i++) ans += Sum2[i];
return ans;
}
void Process(int idx)
{
for(auto a: e[idx]) {
if(a.type == 0) {
update(a.l);
}
else if(a.type == 1) {
Ans[a.Time] = Q2(a.l,a.r);
}
else if(a.type == 2) {
Ans[a.Time] = Q1(a.l,a.r);
}
}
for(int i=0;i<RootN;i++) Sum1[i] = Sum2[i] =0;
for(auto a: e[idx]) {
if(a.type == 0) {
Arr1[a.l]=0;
Arr2[a.l]=0;
}
}
}
int main()
{
in3(n,m,q);
POW[0]=1;
for(int i=1;i < N;i ++) {
POW[i] = (POW[i-1] * BASE ) % mod;
}
block = sqrt(n)+1;
for(int i=0;i<n;i++){
id[i] = i/block;
if(i%block==0){
Beg[id[i]] = i;
End[id[i]] = min(n-1, (id[i] + 1) * block - 1) ;
}
}
for(int i=0;i<m;i++){
scanf("%s",str);
reverse(str,str+strlen(str));
value[i] = H(str);
len[i] = strlen(str);
Map[value[i]] = i;
uniqueLen[i] = len[i];
}
sort(uniqueLen, uniqueLen + m);
TLen = unique(uniqueLen, uniqueLen + m) - uniqueLen;
int t,l,r,p;
char ch;
for(int i=0;i<q;i++) {
scanf("%d",&t);
if(t==0) {
scanf("%d %c",&l,&ch);
l--;
append(l,ch);
}
else if(t==1) {
scanf("%d %d %d",&l,&r,&p);
l--,r--,p--;
e[p].push_back({1,l,r,i});
}
else if(t==2) {
scanf("%d %d %d",&l,&r,&p);
l--,r--,p--;
e[p].push_back({2,l,r,i});
}
}
ms(Ans,-1);
for(int i=0;i<m;i++) {
Process(i);
}
for(int i= 0;i < q;i ++) if(Ans[i] >= 0)printf("%lld\n",Ans[i]);
return 0;
}
Code for Fun 