https://toph.co/p/another-query-on-string

1 x ch
Change the x^th character of S to ch (i.e. S[x] = ch).
2 L R ch
Count the number of occurrences of ch between indices L and R in S. That means, you have to count number of such indices i where S[i] == ch.

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fast ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define filein freopen("input.txt","r",stdin)
#define fileout freopen("output.txt","w",stdout)
using namespace std;
int n,m;
string str ;
int ara[100009];
int tree[100009*4][27];
void init(int node,int b, int e,char ch)
{
    if(b==e)
    {
        tree[node][ch-'a']= {str[b-1]==ch};
        return ;
    }
    int mid=(b+e)>>1;
    int left=node<<1;
    int right=left+1;
    init(left, b,mid,ch);
    init(right,mid+1,e,ch);
    tree[node][ch-'a']=tree[left][ch-'a']+tree[right][ch-'a'];
}
void update(int node,int b, int e, int i, char ch, int value)
{
    if(e<i or b>i)
        return ;
    if(b>=i and e<=i)
    {
        tree[node][ch-'a']=value;
        return ;
    }
    int mid=(b+e)>>1;
    int left=node<<1;
    int right=left+1;
    update(left, b,mid,i,ch,value);
    update(right,mid+1,e,i,ch,value);
    tree[node][ch-'a']=tree[left][ch-'a']+tree[right][ch-'a'];
}
int  query(int node,int b, int e, int i,int j,char ch)
{
    if(e<i or b>j)
        return 0;
    if(b>=i and e<=j)
    {
        return tree[node][ch-'a'];
    }
    int mid=(b+e)>>1;
    int left=node<<1;
    int right=left+1;
    int x=query(left, b,mid,i,j,ch);
    int y=query(right,mid+1,e,i,j,ch);
    return x+y;
}
bool check[80];
int  main()
{
    cin>>n>>m;
    cin>>str;
    for( int i=0; i<n; i++)
    {
        if(check[str[i]-'a']==false)
        {
            check[str[i]-'a']=true;
            init(1,1,n,str[i]);
        }
    }
    while(m--)
    {
        int a;
        cin>>a;
        if(a==1)
        {
            int b;
            char ch;
            cin>>b>>ch;
            if(str[b-1]!=ch)
            {
                update(1,1,n,b,ch,1) ;
                update(1,1,n,b,str[b-1],0);
                str[b-1]=ch;
            }

        }
        else
        {
            int a1,b;
            char ch;
            cin>>a1>>b>>ch;
            cout<<query(1,1,n,a1,b,ch)<<'\n';

        }
    }

}

Light oj 1207 Solution (SEGMENT TREE)

INPUT:

1

5

1 4

2 6

8 10

3 4

7 10

OUTPUT:
Case 1: 4

For each case, print the case number and the number of posters with visible sections.

#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cctype>
#include <cstdio>
#include <iomanip>
#include <sstream>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <complex>
#include <numeric>
#include <valarray>
#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
#define inf (1<<29)
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define nl printf("\n")
#define spc printf(" ")
#define sci(n) scanf("%ld",&n)
#define sc64(n) scanf("%I64d",&n)
#define scii(a,b) scanf("%ld %ld",&a,&b)
#define sc6464(a,b) scanf("%I64d %I64d",&a,&b)
#define scs(s) scanf("%s",s)
#define scss(a,b) scanf("%s %s",a,b)
#define scd(f) scanf("%lf",&f)
#define scdd(a,b) scanf("%lf %lf",&a,&b)
#define pfi(a) printf("%ld",a)
#define pf64(a) printf("%I64d",a)
#define pfii(a,b) printf("%ld %ld",a,b)
#define pf6464(a,b) printf("%I64d %I64d",a,b)
#define pfs(a) printf("%s",a)
#define pfss(a,b) printf("%s %s",a,b)
#define pfd(a) printf("%lf",a)
#define pfdd(a,b) printf("%lf %lf",a,b)
#define rep(i,n) for(int i(0),_n(n);i<_n;++i)
#define repr(i,n) for(int i=n;i>=0;i--)
#define repi(i,a,b) for(int i(a),_b(b);i<=_b;++i)
#define repl(i,n) for(int i(1),_n(n);i<=_n;++i)
#define repir(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define mem(x,a) memset(x,a,sizeof(x))
#define repe(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
int dx[]= {0,0,1,-1,1,-1,1,-1},dy[]= {1,-1,0,0,1,-1,-1,1};
typedef vector<int> vi;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef vector<string> vs;
#define ll long long
typedef vector<vector<int> > vvi;
#else
#define debug(args...)
#endif
#define MX 300000
long long tree[3*MX];
long long ar[MX],tr[3*MX];
set<long>st;
int qq(long l,long r,long i,long j,long node,long valu)
{
    if(i>r||j<l)
        return 0;
    if(tree[node]!=-1)
    {
        if(r!=l)
        {
            tree[node*2]=tree[node];
            tree[node*2+1]=tree[node];
            tree[node]=-1;
        }
    }
    if(i<=l&&j>=r)
    {
        tree[node]=valu;
        return 0;
    }
    long mid=(l+r)/2;
    long left=2*node;
    long right=left+1;
    qq(l,mid,i,j,left,valu);
    qq(mid+1,r,i,j,right,valu);
}
int q(long l,long r,long node)
{
    if(tree[node]!=-1)
    {
        st.insert(tree[node]);
        return 0;
    }
    if(r==l)
        return 0;
    long mid=(l+r)/2;
    long left=2*node;
    long right=left+1;
    q(l,mid,left);
    q(mid+1,r,right);
}
int main()
{
    long t,k;
    scanf("%ld",&t);
    for(long k=1; k<=t; k++)
    {
        long N=1,n,m,f,l,r,val,x,y,gc;
        scanf("%ld",&n);
        n=n*2;
        mem(tree,-1);
        st.clear();
        for(int i=1; i<=n/2; i++)
        {
            scanf("%ld %ld",&l,&r);
            qq(1,n,l,r,1,i);
        }
        q(1,n,1);
        printf("Case %ld: ",k);
        printf("%ld\n",st.size());
    }
    return 0;
}

The maximum possible product of digits among all integers from 1 to n.

In the first example the maximum product is achieved for 389$389$ (the product of digits is 3⋅8⋅9=216$3\cdot 8\cdot 9=216$).

In the second example the maximum product is achieved for 7$7$ (the product of digits is 7$7$).

In the third example the maximum product is achieved for 999999999$999999999$ (the product of digits is 99=387420489$9^9=387420489$).

#include<bits/stdc++.h>
using namespace std;

#define fi(i,a,b)    for(long long i=a;i<=b;i++)
#define fr(i,a)      for(long long i=0;i<a;i++)
#define fd(i,a,b)    for(long long i=b;i>=a;i--)
#define clr(x)       memset(x,0,sizeof(x))
#define cln(x)       memset(x,-1,sizeof(x))
#define __           printf(" ")
#define _            printf("\n")
#define _o           printf("1\n")
#define stree        long long lft=node<<1,rht=(node<<1)|1,mid=(s+e)>>1
#define snode        long long s,long long e,long long node
#define slft         s,mid,lft
#define srht         mid+1,e,rht
#define sin()        if(S<=s&&e<=E)
#define sout()       if(S>e||s>E)
#define mod          1000000007
#define read()       freopen("in.txt","r",stdin)
#define write()      freopen("out.txt","w",stdout)
#define sfl(x)       scanf("%I64d",&x)
#define sfll(x,y)    scanf("%I64d %I64d",&x,&y)
#define sflll(x,y,z) scanf("%I64d %I64d %I64d",&x,&y,&z)
#define pfl(x)       printf("%I64d",x)
#define pfll(x,y)    printf("%I64d %I64d",x,y)
#define pflll(x,y,z) printf("%I64d %I64d %I64d",x,y,z)
#define xx           1000000

typedef long long ll;
typedef pair<long long,long long> pll;



main(){
    long long n;
    cin>>n;
    long long cur=1,ans=0,pre=1,v;
    string s;
    while(n){
        s+=(char(n%10)+'0');
        n/=10;
        cur*=9;
    }

    long long sz=s.size();sz--;

    //cout<<s<<" "<<cur<<endl;

    ans=cur/9;

    while(sz>=0){
        v=s[sz]-'0';
        cur/=9;
        ans=max(ans,max(pre*(v-1)*cur,pre*v));
        pre*=v;
        sz--;
    }
    cout<<ans<<endl;




    return 0;
}






Again


//#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
#include<cstdio>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
#include<map>
#include<set>
#include<queue>
#include<set>
#include<cmath>
#include<cstdlib>
#define pi                  acos(-1)
#define READ                freopen("in.txt", "r", stdin)
#define WRITE               freopen("out.txt", "w", stdout)
#define INF9                 1000000010
#define INF18               1000000000000000010
#define dist(ax,ay,bx,by)   sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by))
#define mod                  1000000007
#define gcd(a,b)            __gcd(a,b)
#define lcm(a,b)            (a*b)/__gcd(a,b)
#define m_p(a,b)            make_pair(a,b)
#define pb                  push_back
#define bpll(a)             __builtin_popcountll(a)
#define MX                  100005

typedef long long lli;
typedef unsigned long long llu;
using namespace std;

vector<lli>ara;



lli func(lli idx, bool small)
{
//    cout<<idx<<endl;
    if(idx==ara.size()) return 1;

    lli ret=0;
    if(small)
    {
        ret= 9*func(idx+1, small);
    }
    else
    {
        ret=0;
        for(lli i=1; i<ara[idx]; i++)
        {
            ret= max(ret, i*func(idx+1, true));
        }
        ret= max(ret, ara[idx]*func(idx+1, small));
    }
    return ret;
}


int main()
{
    lli n;

    cin>>n;

    while(n)
    {
        lli rem= n%10;
        ara.push_back(rem);
        n/=10;
    }

    reverse(ara.begin(), ara.end());

    lli ans= func(0, false);
    ans= max(ans, func(1, true));
    cout<<ans<<endl;


    return 0;
}

UVA 10190- Divide, But Not Quite Conquer!

#include<stdio.h>
long d[200000002];
int main()
{
    long p,m;
    while(scanf("%ld%ld",&p,&m)!=EOF)
    {
        long n,c,j,k=0,s=0,q=0,l,count=0;
        l=p;
        if(p<2||m<2)
        {
            s=1;
        }
        else
        {
            for(k=0; p>1; k++)
            {
                if(p%m!=0)
                {
                    s=1;
                    break;
                }
                else
                {
                    count=count+1;
                    p=p/m;
                    d[k]=p;
                }
            }
        }
        if(s==1)
            printf("Boring!\n");
        else
        {
            printf("%ld",l);
            for(j=0; j<count; j++)
                printf(" %ld",d[j]);
            printf("\n");
        }
    }
    return 0;
}

Bitwise sieve

#include<bits/stdc++.h>
using namespace std;
#define M 100000000
bool check(long long N,long long pos)
{
    return (bool)(N&(1<<pos));
}
long long setit(long long N,long long pos)
{
    return N=(N|(1<<pos));
}
long long status[(M/32)+5],i,j;
vector<long long>vec;
void bit_sieve()
{
    for(i=3;i<=sqrt(M);i+=2)
    {
        if(check(status[i/32],i%32)==0)
        {
            for(j=i*i;j<=M;j+=i*2)
            {
                status[j/32]=setit(status[j/32],j%32);
            }
        }
    }
    vec.push_back(2);
    for(i=3;i<=M;i+=2)
    {
        if(check(status[i/32],i%32)==0)
        {
            vec.push_back(i);
        }
    }
}
main()
{
    bit_sieve();
    long long sz=vec.size();
    cout<<sz<<endl;
}

Light oj :- 1188 - Fast Queries( form i j, you have to find the number of distinct integers from index i to j)

Input

8 5

1 1 1 2 3 5 1 2

1 8

2 3

3 6

4 5

4 8

Output:

Case 1:

4

1

4

2

4

BY Segment tree:

#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cctype>
#include <cstdio>
#include <iomanip>
#include <sstream>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <complex>
#include <numeric>
#include <valarray>
#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
#define inf (1<<29)
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define nl printf("\n")
#define spc printf(" ")
#define sci(n) scanf("%ld",&n)
#define sc64(n) scanf("%I64d",&n)
#define scii(a,b) scanf("%ld %ld",&a,&b)
#define sc6464(a,b) scanf("%I64d %I64d",&a,&b)
#define scs(s) scanf("%s",s)
#define scss(a,b) scanf("%s %s",a,b)
#define scd(f) scanf("%lf",&f)
#define scdd(a,b) scanf("%lf %lf",&a,&b)
#define pfi(a) printf("%ld",a)
#define pf64(a) printf("%I64d",a)
#define pfii(a,b) printf("%ld %ld",a,b)
#define pf6464(a,b) printf("%I64d %I64d",a,b)
#define pfs(a) printf("%s",a)
#define pfss(a,b) printf("%s %s",a,b)
#define pfd(a) printf("%lf",a)
#define pfdd(a,b) printf("%lf %lf",a,b)
#define rep(i,n) for(int i(0),_n(n);i<_n;++i)
#define repr(i,n) for(int i=n;i>=0;i--)
#define repi(i,a,b) for(int i(a),_b(b);i<=_b;++i)
#define repl(i,n) for(int i(1),_n(n);i<=_n;++i)
#define repir(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define mem(x,a) memset(x,a,sizeof(x))
#define repe(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
int dx[]={0,0,1,-1,1,-1,1,-1},dy[]={1,-1,0,0,1,-1,-1,1};
typedef vector<int> vi;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef vector<string> vs;
#define ll long long
typedef vector<vector<int> > vvi;
#define MX 100060
long long tree[3*MX];
long long ar[MX],tr[3*MX],ss=0;
void  update(long l,long r,long i,long j,long node,long valu)
{
    if(i<=l&&j>=r)
    {
       tree[node]=valu;
        return;
    }
    if(i>r||j<l)
    return;

    long mid=(l+r)/2;

    long left=2*node;

    long right=left+1;

    update(l,mid,i,j,left,valu);

    update(mid+1,r,i,j,right,valu);

    tree[node]=tree[left]+tree[right];
}
void csum(long l,long r,long i,long j,long node)
{
    if(i<=l&&j>=r)
    {
        ss+=tree[node];
        return;
    }
    if(i>r||j<l)
    {
      return;
    }
    long mid=(l+r)/2;
    long left=2*node;
    long right=left+1;
    csum(l,mid,i,j,left);
    csum(mid+1,r,i,j,right);
}
int main()
{
    long n,q,a,b,pp;

    scanf("%ld",&pp);

    for(int ii=0;ii<pp;ii++)
    {
        scanf("%ld %ld",&n,&q);

    for(int i=1;i<=n;i++)
    scanf("%ld",&ar[i]);

    long s;

   vector<long>vc[100000],vt[100090];



    long aa[110000]={0},bb[100100]={0};

    for(int i=0;i<q;i++)
    {
        scanf("%ld%ld",&a,&b);

        vc[b].push_back(a);
        vt[b].push_back(i);

    }
    for(int i=1;i<=n;i++)
    {
       if(aa[ar[i]]!=0)
       {
           update(1,n,aa[ar[i]],aa[ar[i]],1,0);
       }

       update(1,n,i,i,1,1);
       //  for(int j=0;j<=15;j++)
       // cout<<tree[j]<<" ";
      // cout<<"\n";
       aa[ar[i]]=i;
       for(int j=0;j<vc[i].size();j++)
       {
           ss=0;
           csum(1,n,vc[i][j],i,1);
           //cout<<ss<<"\n";
           bb[vt[i][j]]=ss;
       }
    }
     printf("Case %ld:\n",ii+1);
    for(int i=0;i<q;i++)
    {
       printf("%ld\n",bb[i]);

    }
    }
return 0;
}


BY Binary indexed tree:


#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<map>

using namespace std;

#define sf scanf
#define pf printf

typedef map<int, int>mpii;

const int high = 100003;

struct Query
{
    int L , R , i;
}q[50007];

int ar[high] , ans[50007] , block=0 , answer=0 , mp[high];

bool cmp(Query x , Query y)
{
    if(x.L/block != y.L/block) return x.L/block < y.L/block;

    return x.R < y.R;
}

void add(int pos)
{
    mp[ar[pos]]++;

    if(mp[ar[pos]] == 1) answer++;
}

void rmoving(int pos)
{
    mp[ar[pos]]--;

    if(mp[ar[pos]] == 0) answer--;
}

void Results(int n , int m)
{
    block = (int)sqrt(n);

    sort(q , q+m , cmp);

    int i , currR = 0 , currL = 0 , L , R;

    for(i=0; i<m; i++)
    {
        L = q[i].L;
        R = q[i].R;

        while(currL < L)
        {
            rmoving(currL);
            currL++;
        }

        while(currL > L)
        {
            add(currL-1);
            currL--;
        }

        while(currR <= R)
        {
            add(currR);
            currR++;
        }

        while(currR > R+1)
        {
            rmoving(currR-1);
            currR--;
        }

        int indx = q[i].i;

        ans[indx] = answer;
    }
}

void solution(int m)
{
    for(int i=0; i<m; i++)
    {
        pf("%d\n" , ans[i]);
    }
}

int main()
{
    int t , tc=0 , n , i , qry , x , y;
    sf("%d", &t);
    while(t--)
    {
        memset(mp , 0 , sizeof mp);

        answer = 0;

        sf("%d %d", &n , &qry);

        for(i=0; i<n; i++)
        {
            sf("%d", &ar[i]);
        }

        for(i=0; i<qry; i++)
        {
            //sf("%d %d", &q[i].L , &q[i].R);

            scanf("%d", &x);
            scanf("%d", &y);
            x--;
            y--;
            q[i].L = x;
            q[i].R = y;
            q[i].i = i;

            q[i].i = i;
        }

        Results(n , qry);

        pf("Case %d:\n" , ++tc);

        solution(qry);
    }

    return 0;
}

1236 - Pairs Forming LCM (Important)

long long pairsFormLCM( int n ) {
    long long res = 0;
    for( int i = 1; i <= n; i++ )
        for( int j = i; j <= n; j++ )
           if( lcm(i, j) == n ) res++; // lcm means least common multiple
    return res;
}


#include <bits/stdc++.h>
#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))
using namespace std;
#define maxx 10000007
bitset<maxx/2>vis;
vector<int>prime;

void sieve()
{
    int x=maxx/2, y=sqrt(maxx)/2;
    for(int i=1;i<=y;i++)
    {
        if(vis[i]==0)
        {
            for(int j=(i*(i+1)*2);j<x;j+=(2*i)+1)
                vis[j]=1;
        }
    }
    prime.pb(2);
    for(int i=3;i<maxx;i+=2)
        if(vis[i/2]==0)
        prime.pb(i);
}

int main()
{
    sieve();
    int t;
    sf(t);
    TEST_CASE(t)
    {
        ll n;
        sfl(n);
        ll ans=1;
        ll root=sqrt(n);
        for(int i=0; i<SZ(prime) && prime[i]<=root;i++)
        {
            if(n%prime[i]==0)
            {
                int cnt=0;
                while(n%prime[i]==0)
                {
                    n/=prime[i];
                    cnt++;
                }
                ans*=(2*cnt+1);
                root=sqrt(n);
            }
        }
        if(n>1)
        {
            ans*=3;
        }
        PRINT_CASE;
        printf("%lld\n",(ans/2)+1);
    }

    return 0;
}