Spoj – DQUERY

Spoj : DQUERY
Problem Link : http://www.spoj.com/problems/DQUERY/
Method : Segment Tree/ MO’s Algorithm

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

/*------- Constants---- */
#define LMT                     1000006
#define ll                      long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define FOR(i,n)                for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define inf                     1<<30
#define lc                      ((n)<<1)
#define rc                      ((n)<<1 |1)
#define debug(x)                cout <<#x<<" -> " << x << endl;


/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
	register int c = gc();
	x = 0;
	int neg = 0;
	for(;((c<48 | c>57) && c != '-');c = gc());
	if(c=='-') {neg=1;c=gc();}
	for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
	if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
      ll ret = 1;
      for(; e > 0; e >>= 1){
            if(e & 1) ret = (ret * p) % M;
            p = (p * p) % M;
      } return (T)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 ****************************/


int iAr[LMT], A[LMT];
vector<ii> Q[LMT];
int cnt[LMT];
int nxt[LMT];
int T[3*LMT];

void build(int n,int b,int e)
{
      if(b==e) {
            T[n] = A[b];
            return;
      }
      int mid = (b+e)/2;
      build(lc, b, mid) ;
      build(rc, mid+1, e);
      T[n] = T[lc] + T[rc];
}

int query(int n,int b,int e, int i , int j)
{
      if(b>j || e < i ) return 0;
      if(b>= i && e <= j  ) return T[n];
      
      int mid = (b+e)/2;
      return query(lc, b, mid, i , j) + query(rc, mid +1 ,  e, i , j);
}

void upd( int n,int b,int e,int pos)
{
      if(b==e && b == pos ) {
            A[pos] = 1;
            T[n] = 1;
            return;
      }
      int mid = (b+e)/2;
      if(pos <= mid ) upd(lc, b, mid, pos);
      else upd(rc, mid+1, e, pos);
      T[n] = T[lc] + T[rc];
}
int iAns[LMT];

int main()
{
      
      
      int n;
      sc(n);
      for(int i = 1; i <= n ; i ++ ) {
            sc(iAr[i]);
            if(cnt[iAr[i]] > 0 ) {
                  A[i] = 0;
                  nxt[cnt[iAr[i]]] = i ;
                  cnt[iAr[i]] = i;
            }
            else {
                  A[i] = 1;
                  cnt[iAr[i] ] = i ;
            }
            
            
      }
      //for(int i  =1 ; i<= n ;i ++ ) printf("%d %d\n" , i , nxt[i]);
      build(1,1,n);
      
      int q , a ,b ;
      sc(q);
      for(int i  = 0 ;i < q; i ++ ) {
            sc(a);sc(b);
            Q[a].push_back(mp(b, i));
      }
      
      for(int i = 1 ; i <= n ; i ++ ) {
            for(int j = 0 ;j < Q[i].size() ; j ++ ) {
                  int R = Q[i][j].first;
                  int p = query(1, 1, n, i, R);
                  iAns[Q[i][j].second] = p;
            }
            if(nxt[i] >0 ) upd(1, 1, n, nxt[i]);
            
      }
      
      for(int i = 0;i < q; i ++ ) {
            printf("%d\n", iAns[i]);
      }
      
}

জ্যামিতি

আমি নিজেই জ্যামিতি অত ভাল পারি না । তাই এ নিয়ে একটু পড়ি আর লিখি । এই লেখার জন্যে অনেক কিছু পড়তে হয় । এতেই বহুত জ্ঞান ।
আমি এখানে বেশ কিছু টাইপের বিগিনার জ্যামিতি প্রব্লেম গুলো নিয়ে লিখব ।

প্রব্লেম ১ ঃ
লাইট অজিতে জ্যামিতির যে প্রব্লেম টা সবচেয়ে বেশি শলভ হয়েছে সেটি
লিঙ্ক ঃ http://lightoj.com/volume_showproblem.php?problem=1022
http://lightoj.com/volume_showproblem.php?problem=1022
প্রব্লেম টাতে চেয়েছে ঃ একটা Circle আর ব্যাসের সমান বাহুবিশিষ্ট একটা বর্গের ক্ষেত্রফল – ওই Circle এর ক্ষেত্রফল
এখন circle এর ব্যাসার্ধ r হলে ,ব্যাস 2r , বর্গের ক্ষেত্রফল (2r)^2
আর ওই circle এর ক্ষেত্রফল PI * r^2;

#include <stdio.h>
#include <math.h>
int main()
{
 
    int testcase,i;
    scanf("%d",&testcase);
    double radius;
    for (i=1;i<=testcase; i++) {
        scanf("%lf",&radius);
        printf("Case %d: %.2lf\n",i,(4*radius*radius)-2*acos(0.0)*radius*radius);
    }
    return 0;
}