CF: 546-D2-E-Soldier and Traveling

Posted on by
Problem Link : http://codeforces.com/contest/546/problem/E
Solution Idea:

  • We can solve this problem using maxflow. So at first make a source
  • Make a first group of vertices consisting of n vertices, each of them for one city.
  • Connect a source with ith vertex in first group with edge that has capacity ai.
  • Make a sink and second group of vertices in the same way, but use bi except for ai.
  • If there is a road between cities i and j or i = j. Make two edges, first should be connecting ith vertex from first group, and jth vertex from second group, and has infinity capacity. Second should be similar, but connect jth from first group and ith from second group.
  • Then find a maxflow, in any complexity.
  • If maxflow is equal to sum of ai and is equal to sum of bi, then there exists an answer. How can we get it? We just have to check how many units are we pushing through edge connecting two vertices from different groups.

Using Dinitz Maxflow

/*
Author: Tanmoy Datta
Solution Idea:
---------------
- Make a source.
- Make a first group of vertices consisting of n vertices, each of them for one city.
- Connect a source with ith vertex in first group with edge that has capacity ai.
- Make a sink and second group of vertices in the same way, but use bi except for ai.
- If there is a road between cities i and j or i = j. Make two edges, first should be connecting ith vertex from first group,
and jth vertex from second group, and has infinity capacity. Second should be similar, but connect jth from first group and
ith from second group.
- Then find a maxflow, in any complexity.
- If maxflow is equal to sum of ai and is equal to sum of bi, then there exists an answer. How can we get it?
We just have to check how many units are we pushing through edge connecting two vertices from different groups.
*/
///Using MaxFlow Dinitz
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#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 VI vector <int>
#define MOD 1000000007
#define fast_cin ios_base::sync_with_stdio(0); cin.tie(0); cout.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 UNIQUE(v) (v).erase(unique((v).begin(),(v).end()),(v).end())
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
#define NORM(x) if(x>=mod) x-=mod;if(x<0) x+=mod;
#define ODD(x) (((x)&1)==0?(0):(1))
#define loop(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;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 LINE_PRINT_CASE printf("Case %d:\n",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)))
#define D(x) cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define DD(x,y) cerr << __LINE__ << ": " << #x << " = " << x << " " << #y << " = " << y << '\n'
#define DDD(x,y,z) cerr << __LINE__ << ": " << #x << " = " << x << " " << #y << " = " << y << " " << #z << " = " << z << '\n'
#define DBG cerr << __LINE__ << ": Hi" << '\n'
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*------------------------------------------------*/
/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/
///Max Flow Dinitz (Zobayer Vhai)
///clear()
///Build graph by addEdge
///Call findFLOW() to find maximum flow
const int INF = 1<<28; ///INT_MAX
const int MAXN = 4005, MAXE=4005;
///Maximum number of nodes and edges.
int Q[MAXN], fin[MAXN], pro[MAXN], dist[MAXN];
int flow[MAXE], cap[MAXE], nxt[MAXE], to[MAXE];
struct DINITZ
{
int src, snk, nNode, nEdge;
///Parameters: (source, sink, no of nodes)
void clear(int _src, int _snk, int _n)
{
src = _src, snk = _snk;
nNode = _n, nEdge = 0;
memset(fin,-1, sizeof fin);
}
///Parameters: (from, to, capacity)
void addEdge(int u, int v, int _cap)
{
to[nEdge] = v, cap[nEdge] = _cap, flow[nEdge] = 0;
nxt[nEdge] = fin[u];
fin[u] = nEdge++;
///Make this 2nd capacity zero for directed edge
_cap=0;
to[nEdge] = u, cap[nEdge] = _cap, flow[nEdge] = 0;
nxt[nEdge] = fin[v];
fin[v] = nEdge++;
}
bool BFS()
{
int st, en;
memset(dist,-1,sizeof dist);
dist[src] = st = en = 0;
Q[en++] = src;
while(st<en)
{
int u = Q[st++];
for(int i = fin[u]; i>=0; i = nxt[i])
{
int v = to[i];
if(flow[i] < cap[i] && dist[v] == -1)
{
dist[v] = dist[u] + 1;
Q[en++] = v;
}
}
}
return dist[snk] != -1;
}
int DFS(int u, int fw)
{
if(u == snk) return fw;
for(int &e = pro[u]; e >= 0; e = nxt[e])
{
int v = to[e];
if(flow[e] < cap[e] && dist[v] == dist[u] + 1)
{
int cur_flow = DFS(v, min(cap[e]-flow[e], fw));
if(cur_flow > 0)
{
flow[e] += cur_flow;
flow[e^1]-= cur_flow;
return cur_flow;
}
}
}
return 0;
}
long long findFLOW()
{
long long fflow = 0;
while(BFS())
{
for(int i = 0; i<= nNode; i++)
{
pro[i] = fin[i];
}
while(true)
{
long long fw=DFS(src,INF);
if(fw > 0)
fflow += fw;
else
break;
}
}
return fflow;
}
}dinitz;
int A[MAXN],B[MAXN];
int grid[MAXN][MAXN];
int main()
{
//#ifndef ONLINE_JUDGE
//// freopen("in.txt","r",stdin);
//// freopen("out.txt","w",stdout);
//#endif
int sum1=0,sum2=0;
int n,m;
sff(n,m);
dinitz.clear(0,2*n+1,2*n+2);
for(int i=1;i<=n;i++)
{
sf(A[i]);
dinitz.addEdge(0,i,A[i]);
sum1+=A[i];
}
for(int i=1;i<=n;i++)
{
sf(B[i]);
dinitz.addEdge(n+i,2*n+1,B[i]);
sum2+=B[i];
}
for(int i=1;i<=n;i++)
{
dinitz.addEdge(i,n+i,INF);
}
for(int i=0;i<m;i++)
{
int u,v;
sff(u,v);
dinitz.addEdge(u,n+v,INF);
dinitz.addEdge(v,n+u,INF);
}
int ans=dinitz.findFLOW();
if(ans!=sum1 || ans!=sum2)
{
printf("NO\n");
return 0;
}
for(int u=1;u<=n;u++)
{
for(int i=fin[u];i>=0;i=nxt[i])
{
int v=to[i];
if(v>n)
grid[u][v-n]=flow[i];
}
}
printf("YES\n");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d",grid[i][j]);
if(j<n)
printf(" ");
}
printf("\n");
}
return 0;
}
view raw CF546-D2-E-Soldier and Traveling.cpp hosted with ❤ by GitHub

Using Ford Fulkerson Maxflow
///Using Maxflow Ford Fulkerson
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#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 VI vector <int>
#define MOD 1000000007
#define fast_cin ios_base::sync_with_stdio(0); cin.tie(0); cout.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 UNIQUE(v) (v).erase(unique((v).begin(),(v).end()),(v).end())
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
#define NORM(x) if(x>=mod) x-=mod;if(x<0) x+=mod;
#define ODD(x) (((x)&1)==0?(0):(1))
#define loop(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;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 LINE_PRINT_CASE printf("Case %d:\n",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)))
#define D(x) cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define DD(x,y) cerr << __LINE__ << ": " << #x << " = " << x << " " << #y << " = " << y << '\n'
#define DDD(x,y,z) cerr << __LINE__ << ": " << #x << " = " << x << " " << #y << " = " << y << " " << #z << " = " << z << '\n'
#define DBG cerr << __LINE__ << ": Hi" << '\n'
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define mx 105
int n,m;
int a[mx],b[mx];
int g[2*mx][2*mx];
bool vis[2*mx];
int par[2*mx];
bool find_path(int s, int t)
{
ms(vis,0);
queue<int>Q;
Q.push(s);
vis[s]=1;
while(!Q.empty())
{
int u=Q.front();
Q.pop();
if(u==t) return true;
for(int i=0; i<=2*n+1; i++)
{
if(vis[i]==0 && g[u][i]>0)
{
vis[i]=1;
par[i]=u;
Q.push(i);
// if(i==t) return true;
}
}
}
return false;
}
int find_flow(int s, int t)
{
int ret=0;
while(find_path(s,t))
{
int mini=INT_MAX;
for(int i=t; i!=s; i=par[i])
{
int u=par[i];
mini=min(g[u][i],mini);
}
for(int i=t; i!=s; i=par[i])
{
int u=par[i];
g[u][i]-=mini;
g[i][u]+=mini;
}
ret+=mini;
}
return ret;
}
int main()
{
//#ifndef ONLINE_JUDGE
//// freopen("in.txt","r",stdin);
//// freopen("out.txt","w",stdout);
//#endif
sff(n,m);
int total=0,total1=0;
for(int i=1; i<=n; i++)
{
sf(a[i]);
total1+=a[i];
}
for(int i=1; i<=n; i++)
{
sf(b[i]);
total+=b[i];
}
for(int i=0; i<m; i++)
{
int x,y;
sff(x,y);
g[x][n+y]=1e5;
// g[n+y][x]=1e5;
g[y][n+x]=1e5;
// g[n+x][y]=1e5;
}
for(int i=1;i<=n;i++)
{
g[i][n+i]=1e5;
// g[n+i][i]=1e5;
}
for(int i=1; i<=n; i++)
{
g[0][i]=a[i];
}
for(int i=1; i<=n; i++)
{
g[n+i][2*n+1]=b[i];
}
int ans=find_flow(0,2*n+1);
if(ans!=total || ans!=total1)
{
printf("NO\n");
return 0;
}
printf("YES\n");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
// if(i==j)
// g[n+j][i]=max(0,g[n+j][i]-100000);
printf("%d",g[n+j][i]);
if(j<n)
printf(" ");
}
printf("\n");
}
return 0;
}
view raw CF546-D2-E-Soldier and Traveling(Ford Fulkerson).cpp hosted with ❤ by GitHub

SPOJ: MKTHNUM – K-th Number

Posted on by

Problem Link: https://www.spoj.com/problems/MKTHNUM/

Solution Idea: (Merge Sort Tree)

  • At first take input and store the input in a pair array where first element of ith pair is the value ai and second element of ith pair is i.
  • Sort the pair array with with ascending order of ai
  • Build a merge sort tree using the second element of each pair of sorted pair array.
  • Now for each query i,j,k at first check how many number in range i to j inclusive are present in left subtree of current node in merge sort tree. Let the value is x. So if x<=k then it's sure that the answer is in the left subtree. So we will go to left subtree of current node with k. Otherwise we will go to right subtree of current node with k-x;
  • In this manner when we reach to a leaf node we can say that this node contains the index of our answer.


/*
Author: Tanmoy Datta
Solution Idea:
- At first take input and store the input in a pair array where first element of i_th pair is the value a_i and second
element of i_th pair is i.
- Sort the pair array with with ascending order of a_i
- Build a merge sort tree using the second element of each pair of sorted pair array.
- Now for each query i,j,k at first check how many number in range i to j inclusive are present in left subtree of current
node in merge sort tree. Let the value is x. So if x<=k then it's sure that the answer is in the left subtree. So we will
go to left subtree of current node with k. Otherwise we will go to right subtree of current node with k-x;
- In this manner when we reach to a leaf node we can say that this node contains the index of our answer.
*/
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#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 VI vector <int>
#define MOD 1000000007
#define fast_cin ios_base::sync_with_stdio(0); cin.tie(0); cout.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 UNIQUE(v) (v).erase(unique((v).begin(),(v).end()),(v).end())
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
#define NORM(x) if(x>=mod) x-=mod;if(x<0) x+=mod;
#define ODD(x) (((x)&1)==0?(0):(1))
#define loop(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;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 LINE_PRINT_CASE printf("Case %d:\n",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)))
#define D(x) cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define DD(x,y) cerr << __LINE__ << ": " << #x << " = " << x << " " << #y << " = " << y << '\n'
#define DDD(x,y,z) cerr << __LINE__ << ": " << #x << " = " << x << " " << #y << " = " << y << " " << #z << " = " << z << '\n'
#define DBG cerr << __LINE__ << ": Hi" << '\n'
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*------------------------------------------------*/
/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2
#define mx 100005
pii ara[mx];
int arr[mx];
vector<int>tree[3*mx];
void init(int n, int b, int e)
{
if(b==e)
{
tree[n].pb(ara[b].ss);
return;
}
segment_tree;
init(l,b,mid);
init(r,mid+1,e);
merge(all(tree[l]),all(tree[r]),back_inserter(tree[n]));
}
int query(int n, int b, int e, int i, int j, int k)
{
if(b==e)
{
return tree[n].back();
}
segment_tree;
int x = upper_bound(all(tree[l]),j)-lower_bound(all(tree[l]),i);
if(x>=k)
{
return query(l,b,mid,i,j,k);
}
else
return query(r,mid+1,e,i,j,k-x);
}
int main()
{
//#ifndef ONLINE_JUDGE
//// freopen("in.txt","r",stdin);
//// freopen("out.txt","w",stdout);
//#endif
int n,m;
sff(n,m);
for(int i=1;i<=n;i++)
{
sf(ara[i].ff);
ara[i].ss=i;
arr[i]=ara[i].ff;
}
sort(ara+1,ara+n+1);
init(1,1,n);
while(m--)
{
int a,b,c;
sfff(a,b,c);
int ans=query(1,1,n,a,b,c);
ans=arr[ans];
printf("%d\n",ans);
}
return 0;
}
view raw SPOJ: MKTHNUM - K-th Number (Merge Sort Tree).cpp hosted with ❤ by GitHub

Light OJ: 1144 – Ray Gun

Posted on by
Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1144
Solution Idea:

    There are many observations to make in order to get to a working solution.

  • For every lattice point (i, j), the ray that intersects it is unique and it’s identified by the pair , where g is the gcd of i and j.


  • The problem is now reduced to counting the number of irreducible fractions such that a ≤ N and b ≤ M. This is the same as counting for every i between 1 and N, the amount of numbers in the range [1, M] that are coprime with i.


  • Consider a certain number x with prime factors p1, p2. How do we know how many numbers in range [1, M] are coprime with it? That’s equal to M minus the amount of multiples of p1 minus the amount of multiples of p2 plus the amount of multiples of p1 * p2. This is inclusion-exclusion, and in general, if the amount of elements is even, we add, otherwise, we subtract.


  • So now we have a working (but slow) solution: Iterate over every i in the range [1, N] and for every i, factorize it, try out all combinations of primes and then, for every combination that results in a number k, add if the amount of primes is even or subtract if the amount of primes is odd.


  • The previous approach is very slow for two reasons: You’ll be factorizing each number every time and you’ll be doing a lot of repeated work. Every combination of primes you try out at each step will result in a certain number k. A crucial observation is that the higher exponent of that number k will be 1, because we’re trying combinations of different primes. Another crucial observation is that this number k will be seen times in total. Finally, each time we see it, it will contribute by to the final answer (or if the amount of primes is odd).


  • Knowing all this, we can precalculate a lot of stuff and then solve each test case in O(N). We should precalculate the amount of prime factors of every number in the range [1, 106] (this can be done with a simple sieve), and we should cross out numbers that have some prime with an exponent higher than 1 (in other words, multiples of some square). Once we have precalculated all that, we simply iterate from 1 to N and for every number x that we didn’t cross out, we add (or subtract) to our answer.


  • Final observations: We should add 2 to our answer (the two borders). If N = 0, the answer is 1, except M = 0 too, in which case the answer is 0.



    • (This solution idea is from this link )

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#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) cerr<<#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); cout.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 loop1(i,n) for(int i=1;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 LINE_PRINT_CASE printf("Case %d:\n",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;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*------------------------------------------------*/
/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/
#define mx 1000006
ll mobius[mx];
bool vis[mx];
ll n,m;
void precal()
{
for(int i=2;i<mx;)
{
for(int j=i+i;j<mx;j+=i)
mobius[j]++;
for(++i;;i++)
if(mobius[i]==0) break;
}
for(int i=2;i<mx;i++)
{
if(mobius[i]==1)
{
for(int j=i;j<mx;j+=i)
vis[j]=1;
}
}
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t;
sf(t);
precal();
TEST_CASE(t)
{
sffl(n,m);
if(n>m) swap(n,m);
ll ans=n*m;
// ms(mobius,0);
// ms(vis,0);
for(ll i=2;i<=n;i++)
{
if(vis[i]==1) continue;
ll x=(m/i)*(n/i);
if(mobius[i]==0)
ans-=x;
else if(mobius[i]%2==1)
ans-=x;
else
ans+=x;
// for(ll j=i;j<=n;j*=i) vis[j]=1;
}
if(n) ans++;
if(m) ans++;
PRINT_CASE;
printf("%lld\n",ans);
}
return 0;
}
view raw Light OJ 1144 - Ray Gun.cpp hosted with ❤ by GitHub

SPOJ: GSS2 – Can you answer these queries II

Posted on by

Problem Link : http://www.spoj.com/problems/GSS2/


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#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)             cerr<<#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); cout.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 loop1(i,n)       for(int i=1;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 LINE_PRINT_CASE  printf("Case %d:\n",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;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 100005
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2


int ara[mx+5];
int last[2*mx+5];
ll ans[mx+5];

struct data
{
    int l,r,id;
};

vector<data>queries;

struct data1
{
    ll sum,lazy,best_lazy,ans;
    data1()
    {
        sum=lazy=best_lazy=ans=0;
    }
};

data1 tree[3*mx];

void push_down(data1 &cur, data1 &lft, data1 &rgt)
{
//    if(cur.lazy || cur.best_lazy)
//    {
        lft.best_lazy=max(lft.best_lazy,lft.lazy+cur.best_lazy);
        lft.lazy+=cur.lazy;
        lft.ans=max(lft.ans,lft.sum+cur.best_lazy);
        lft.sum=lft.sum+cur.lazy;
        rgt.best_lazy=max(rgt.best_lazy,rgt.lazy+cur.best_lazy);
        rgt.lazy+=cur.lazy;
        rgt.ans=max(rgt.ans,rgt.sum+cur.best_lazy);
        rgt.sum+=cur.lazy;
        cur.lazy=cur.best_lazy=0;
//    }
}

void push_up(data1 &cur, data1 &lft, data1 &rgt)
{
    cur.ans=max(lft.ans,rgt.ans);
    cur.sum=max(lft.sum,rgt.sum);
}


void update(int n, int b, int e, int i, int j, ll val)
{
    if(b>j || e<i) return;
    if(b>=i && e<=j)
    {
        tree[n].best_lazy=max(tree[n].best_lazy,tree[n].lazy+val);
        tree[n].lazy+=val;
        tree[n].ans=max(tree[n].ans,tree[n].sum+val);
        tree[n].sum+=val;
        return;
    }
    segment_tree;
    push_down(tree[n],tree[l],tree[r]);
    update(l,b,mid,i,j,val);
    update(r,mid+1,e,i,j,val);
    push_up(tree[n],tree[l],tree[r]);
}

data1 query(int n, int b, int e, int i, int j)
{
    if(b>j || e<i) return data1();
    if(b>=i && e<=j)
    {
        return tree[n];
    }
    segment_tree;
    push_down(tree[n],tree[l],tree[r]);
    data1 p=query(l,b,mid,i,j);
    data1 q=query(r,mid+1,e,i,j);
    data1 ret;
    push_up(ret,p,q);
    return ret;
}


int main()
{

//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);
    int n;
    sf(n);
    for(int i=1; i<=n; i++) sf(ara[i]);
    int m;
    sf(m);
    data a;
    for(int i=0; i<m; i++)
    {
        sff(a.l,a.r);
        a.id=i;
        queries.pb(a);
    }

    sort(all(queries),[](data a,data b)
    {
        return a.r<b.r;
    });

    int idx=0;
    for(int i=1; i<=n && idx<SZ(queries); i++)
    {
//        if(last[mx+ara[i]]!=0)
//        {
//            update(1,1,n,last[mx+ara[i]],0);
//        }
        int xx=last[mx+ara[i]]+1;
        update(1,1,n,xx,i,ara[i]);
        last[mx+ara[i]]=i;
        while(idx<SZ(queries) && queries[idx].r==i)
        {
            ans[queries[idx].id]=query(1,1,n,queries[idx].l,queries[idx].r).ans;
            idx++;
        }
    }

    for(int i=0; i<m; i++)
        printf("%lld\n",ans[i]);



    return 0;
}

SPOJ: CERC07S – Robotic Sort

Posted on by

Problem Link : http://www.spoj.com/problems/CERC07S/

Solution Idea:


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#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)             cerr<<#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); cout.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 loop1(i,n)       for(int i=1;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 LINE_PRINT_CASE  printf("Case %d:\n",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;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/


/*-------------------------Treap Start------------------------*/
struct node
{
    int prior,size;
    pii val;//value stored in the array
    pii mini;//whatever info you want to maintain in segtree for each node
    int lazy;//whatever lazy update you want to do
    int id;
    struct node *l,*r;
};

typedef node* pnode;

int sz(pnode t)
{
    return t?t->size:0;
}

void upd_sz(pnode t)
{
    if(t)t->size=sz(t->l)+1+sz(t->r);
}

void lazy(pnode t)
{
    if(!t || !t->lazy)return;
//    t->val+=t->lazy;//operation of lazy
//    t->mini+=t->lazy*sz(t);
    swap(t->l,t->r);
    if(t->l)t->l->lazy^=t->lazy;//propagate lazy
    if(t->r)t->r->lazy^=t->lazy;
    t->lazy=0;
}

void reset(pnode t)
{
    if(t)t->mini = t->val;//no need to reset lazy coz when we call this lazy would itself be propagated
}

void combine(pnode& t,pnode l,pnode r) //combining two ranges of segtree
{
    if(!l || !r)return void(t = l?l:r);
    t->mini = min(l->mini, r->mini);
}

void operation(pnode t) //operation of segtree
{
    if(!t)return;
    reset(t);//reset the value of current node assuming it now represents a single element of the array
    lazy(t->l);
    lazy(t->r);//imp:propagate lazy before combining t->l,t->r;
    combine(t,t->l,t);
    combine(t,t,t->r);
}

void split(pnode t,pnode &l,pnode &r,int pos,int add=0)
{
    if(!t)return void(l=r=NULL);
    lazy(t);
    int curr_pos = add + sz(t->l);
    if(curr_pos<=pos)//element at pos goes to left subtree(l)
        split(t->r,t->r,r,pos,curr_pos+1),l=t;
    else
        split(t->l,l,t->l,pos,add),r=t;
    upd_sz(t);
    operation(t);
}

int find_min(pnode t, int add=0)
{
    lazy(t);
    int cur_pos=sz(t->l)+add;
    if(t->r && t->r->mini==t->mini) return find_min(t->r,cur_pos+1);
    if(t->l && t->l->mini==t->mini) return find_min(t->l,add);
    return cur_pos;
}

void merge(pnode &t,pnode l,pnode r)  //l->leftarray,r->rightarray,t->resulting array
{
    lazy(l);
    lazy(r);
    if(!l || !r) t = l?l:r;
    else if(l->prior>r->prior)merge(l->r,l->r,r),t=l;
    else    merge(r->l,l,r->l),t=r;
    upd_sz(t);
    operation(t);
}

pnode init(int val, int id)
{
    pnode ret = (pnode)malloc(sizeof(node));
    ret->prior=rand();
    ret->size=1;
    ret->val=pii(val,id);
    ret->mini=pii(val,id);
    ret->lazy=0;
    ret->l=ret->r=NULL;
    return ret;
}

//int range_query(pnode t,int l,int r) //[l,r]
//{
//    pnode L,mid,R;
//    split(t,L,mid,l-1);
//    split(mid,t,R,r-l);//note: r-l!!
//    int ans = t->mini;
//    merge(mid,L,t);
//    merge(t,mid,R);
//    return ans;
//}

//void range_update(pnode t,int l,int r,int val) //[l,r]
//{
//    pnode L,mid,R;
//    split(t,L,mid,l-1);
//    split(mid,t,R,r-l);//note: r-l!!
//    t->lazy+=val; //lazy_update
//    merge(mid,L,t);
//    merge(t,mid,R);
//}

//void split(pnode t,pnode &l,pnode &r,int key)
//{
//    if(!t) l=r=NULL;
//    else if(t->val<=key) split(t->r,t->r,r,key),l=t; //elem=key comes in l
//    else split(t->l,l,t->l,key),r=t;
//    upd_sz(t);
//}
//
//void insert(pnode &t,pnode it)
//{
//    if(!t) t=it;
//    else if(it->prior>t->prior) split(t,it->l,it->r,it->val),t=it;
//    else insert(t->val<=it->val?t->r:t->l,it);
//    upd_sz(t);
//}
//
//void erase(pnode &t,int key)
//{
//    if(!t)return;
//    else if(t->val==key)
//    {
//        pnode temp=t;
//        merge(t,t->l,t->r);
//        free(temp);
//    }
//    else erase(t->val<key?t->r:t->l,key);
//    upd_sz(t);
//}

void output(pnode t)
{
    if(!t) return;
    output(t->l);
    printf("%d ",t->val);
    output(t->r);
}

void clear_tree(pnode t)
{
    if(!t) return;
    clear_tree(t->l);
    clear_tree(t->r);
    free(t);
}

/*-------------------------Treap End--------------------------*/


int main()
{

//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int n;
    while(sf(n) && n)
    {
        pnode root=NULL;
        for(int i=0; i<n; i++)
        {
            int a;
            sf(a);
            merge(root,root,init(a,i+1));
        }
        vector<int>ans;
        while(n)
        {
            int k=find_min(root);
            pnode l,r;
            split(root,l,r,k-1);
            split(r,root,r,0);
            if(l)
                l->lazy=1;
            merge(root,l,r);
            n--;
            ans.pb(SZ(ans)+k+1);
        }

        for(int i=0; i<SZ(ans); i++)
        {
            printf("%d",ans[i]);
            if(i!=SZ(ans)-1)
                printf(" ");
        }
        printf("\n");
//        clear_tree(root);

    }

    return 0;
}

Light OJ: 1267 – Points in Rectangle (II)

Posted on by

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1267

Solution Idea:

    This problem is similar to Codeforces gym 101484: B. Nicoleta’s Cleaning . We need line sweep technique and some data structure to solve this problem. We need to convert each rectangle to opening and closing with respective to it’s x coordinates. Then we need to sort all points and opening and closing together. then for each opening element we need to count how many points are before opening point let is is X and for each closing we need to count how many points are before and on the closing point in the range lower y coordinate to upper y coordinate let it is Y. Then the the number of points inside the rectangle is Y-X. For each given point we need to update it when we find it through scan line in x coordinate of it. 

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#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)             cerr<<#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); cout.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 loop1(i,n)       for(int i=1;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 LINE_PRINT_CASE  printf("Case %d:\n",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;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

struct data
{
    int type,x,st,ed,id;
};

vector<int>x,y;
vector<data>v;

bool cmp(data a, data b)
{
    if(a.x<b.x) return true;
    if(a.x==b.x)
        return a.type<b.type;
    return false;
}

#define mx 300005

int tree[mx];

void update(int idx, int val)
{
    for(; idx<mx && idx; idx+=(idx&-idx))
        tree[idx]+=val;
}

int query(int idx)
{
    int ret=0;
    for(; idx; idx-=(idx&-idx))
        ret+=tree[idx];
    return ret;
}

int ans[mx];

int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);
    int t;
    sf(t);
    TEST_CASE(t)
    {
        int n,m;
        sff(n,m);
        for(int i=0; i<n; i++)
        {
            int a,b;
            sff(a,b);
            data temp;
            temp.type=2;
            temp.x=a;
            temp.ed=temp.st=b;
            v.pb(temp);
            x.pb(a);
            y.pb(b);
        }

        for(int i=0; i<m; i++)
        {
            int a,b,c,d;
            sff(a,b);
            sff(c,d);
            x.pb(a);
            x.pb(c);
            y.pb(b);
            y.pb(d);
            data temp;
            temp.type=3;
            temp.x=c;
            temp.st=b;
            temp.ed=d;
            temp.id=i;
            v.pb(temp);
            data temp1;
            temp1.type=1;
            temp1.x=a;
            temp1.st=b;
            temp1.ed=d;
            temp1.id=i;
            v.pb(temp1);
        }

//    sort(all(x));
        sort(all(y));
        sort(all(v),cmp);

        for(int i=0; i<SZ(v); i++)
        {
            data temp=v[i];
            if(temp.type==1)
            {
                int a=lower_bound(all(y),temp.st)-y.begin()+1;
                int b=lower_bound(all(y),temp.ed)-y.begin()+1;
                int xx=query(b);
                int yy=query(a-1);
                ans[temp.id]=xx-yy;
            }
            else if(temp.type==3)
            {
                int a=lower_bound(all(y),temp.st)-y.begin()+1;
                int b=lower_bound(all(y),temp.ed)-y.begin()+1;
                int xx=query(b);
                int yy=query(a-1);
                ans[temp.id]=(xx-yy)-ans[temp.id];
            }
            else
            {
                int a=lower_bound(all(y),temp.st)-y.begin()+1;
                update(a,1);
//            int yy=query(a-1); // Never do this while range update on BIT -_-
//            ans[temp.id]=xx;
            }
        }

        LINE_PRINT_CASE;
        for(int i=0; i<m; i++)
            printf("%d\n",ans[i]);
        ms(tree,0);
        x.clear();
        y.clear();
        v.clear();
    }
    return 0;
}

Codeforces gym 101484: B. Nicoleta’s Cleaning

1
Posted on by

Problem Link : http://codeforces.com/gym/101484/problem/B

Solution Idea:

    To solve this problem we need line sweep technique and some data structure. At first convert each rectangle in two element with respect to it x coordinate which both x coordinate have same y coordinates. Now call first x point opening and 2nd x point closing of a rectangle. Now take a array of custom data type. and store every opening and closing of rectangles and the query points and sort the the array in the basis of x coordinate of each element and in case of a tie take closing element first then query point and then opening point.

    Now run a loop on the x axis and update every range by 1 if we find a opening and by -1 if we find a closing and if we find a query point just query the value of that point.

    Handle the boundary condition carefully. 


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#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)             cerr<<#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); cout.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 loop1(i,n)       for(int i=1;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 LINE_PRINT_CASE  printf("Case %d:\n",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;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

struct data
{
    int type,x,st,ed,id;
};

vector<int>x,y;
vector<data>v;

bool cmp(data a, data b)
{
    if(a.x<b.x) return true;
    if(a.x==b.x)
        return a.type<b.type;
    return false;
}

#define mx 300005

int tree[mx];

void update(int idx, int val)
{
    for(; idx<mx && idx; idx+=(idx&-idx))
        tree[idx]+=val;
}

int query(int idx)
{
    int ret=0;
    for(; idx; idx-=(idx&-idx))
        ret+=tree[idx];
    return ret;
}

int ans[mx];

int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int n,m;
    sff(n,m);
    for(int i=0; i<n; i++)
    {
        int a,b;
        sff(a,b);
        data temp;
        temp.type=2;
        temp.x=a;
        temp.ed=temp.st=b;
        temp.id=i;
        v.pb(temp);
        x.pb(a);
        y.pb(b);
    }

    for(int i=0; i<m; i++)
    {
        int a,b,c,d;
        sff(a,b);
        sff(c,d);
        x.pb(a);
        x.pb(c);
        y.pb(b);
        y.pb(d);
        data temp;
        temp.type=1;
        temp.x=c;
        temp.st=b;
        temp.ed=d;
        v.pb(temp);
        data temp1;
        temp1.type=3;
        temp1.x=a;
        temp1.st=b;
        temp1.ed=d;
        v.pb(temp1);
    }

//    sort(all(x));
    sort(all(y));
    sort(all(v),cmp);

    for(int i=0; i<SZ(v); i++)
    {
        data temp=v[i];
        if(temp.type==1)
        {
            int a=lower_bound(all(y),temp.st)-y.begin()+1;
            int b=lower_bound(all(y),temp.ed)-y.begin()+1;
            update(a+1,-1);
            update(b,+1);
        }
        else if(temp.type==3)
        {
            int a=lower_bound(all(y),temp.st)-y.begin()+1;
            int b=lower_bound(all(y),temp.ed)-y.begin()+1;
            update(a+1,+1);
            update(b,-1);
        }
        else
        {
            int a=lower_bound(all(y),temp.st)-y.begin()+1;
            int xx=query(a);
//            int yy=query(a-1); // Never do this while range update on BIT -_-
            ans[temp.id]=xx;
        }
    }


    for(int i=0; i<n; i++)
        printf("%d\n",ans[i]);

    return 0;
}

Hackerrank: Solve the Queries!

Posted on by

Problem Link : https://www.hackerrank.com/contests/womens-codesprint-4/challenges/solve-the-queries

Solution Idea:

    The main observation in this problem is the given numbers are <=100 and there are 25 prime number less than 100. As we need to answer whether a range multiplication is multiple of another range multiplication or not.

    We know when we multiply two number their prime power is added. For example 12*18 = (2^2 * 3^1) * (2^1 * 3^2)
    = (2^(2+1) * 3^(1+2))
    = (2^3 * 3^3)
    = 216

    So we can store prime factors of every given number in each segment tree leaf. And while merging two leaf node we need to add each prime power between two two leafs. So a node in the segment tree hold the information about the nubmer in the subtree of this node has how many ith prime divisor.

    Now for each query we can get the power factor of each range from the segment tree and check whether they divides or not and produce the required answer from this prime factors.


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#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)             cerr<<#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); cout.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 loop1(i,n)       for(int i=1;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 LINE_PRINT_CASE  printf("Case %d:\n",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;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int prime[30]= {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int mp[100];

#define mx 50005
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2
struct data
{
    int lazy;
    int ara[25];
};

data ret;

int numbers[mx];
data tree[3*mx];

void func(int n, data &temp, int mul)
{
    ms(temp.ara,0);
    for(int i=0; i<25 && prime[i]*prime[i]<=n; i++)
    {
        if(n%prime[i]==0)
        {
            while(n%prime[i]==0)
            {
                n/=prime[i];
                temp.ara[i]++;
            }
            temp.ara[i]*=mul;
        }
    }

    if(n>1)
        temp.ara[mp[n]]+=mul;
}

void push_up(data &a, data &b, data &c)
{
    for(int i=0; i<25; i++)
        a.ara[i]=b.ara[i]+c.ara[i];
}

void push_down(int n, int b, int e)
{
    if(tree[n].lazy)
    {
        segment_tree;
        func(tree[n].lazy,tree[l],mid-b+1);
        func(tree[n].lazy,tree[r],e-mid);
        tree[l].lazy=tree[n].lazy;
        tree[r].lazy=tree[n].lazy;
        tree[n].lazy=0;
    }
}

void init(int n, int b, int e)
{
    if(b==e)
    {
        tree[n].lazy=0;
        func(numbers[b],tree[n],1);
        return;
    }
    segment_tree;
    init(l,b,mid);
    init(r,mid+1,e);
    push_up(tree[n],tree[l],tree[r]);
}

void update(int n, int b, int e, int i, int j, int val)
{
    if(b>j || e<i) return;
    if(b>=i && e<=j)
    {
        func(val,tree[n],e-b+1);
        tree[n].lazy=val;
        return;
    }
    segment_tree;
    push_down(n,b,e);
    update(l,b,mid,i,j,val);
    update(r,mid+1,e,i,j,val);
    push_up(tree[n],tree[l],tree[r]);
}

data query(int n, int b, int e, int i, int j)
{
    if(b>j || e<i) return ret;
    if(b>=i && e<=j)
    {
        return tree[n];
    }
    push_down(n,b,e);
    segment_tree;
    data p=query(l,b,mid,i,j);
    data q=query(r,mid+1,e,i,j);
    data xx;
    push_up(xx,p,q);
    return xx;
}

ll bigmod(ll n, ll pow, ll mod)
{
    ll rett=1;
    while(pow)
    {
        if(pow%2)
            rett=(rett*n)%mod;
        n=(n*n)%mod;
        pow/=2;
    }
    return rett;
}

int main()
{

//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);
    for(int i=0; i<25; i++) mp[prime[i]]=i;

    int n;
    sf(n);
    loop1(i,n) sf(numbers[i]);

    init(1,1,n);

    int q;
    sf(q);
    while(q--)
    {
        int a;
        sf(a);
        if(a==1)
        {
            int l,r,x;
            sfff(l,r,x);
            update(1,1,n,l,r,x);
        }
        else
        {
            int l, r, p, q, m;
            sff(l,r);
            sff(p,q);
            sf(m);

            data x=query(1,1,n,l,r);
            data y=query(1,1,n,p,q);
            bool valid=1;
            for(int i=0; i<25 && valid; i++)
            {
                x.ara[i]-=y.ara[i];
                if(x.ara[i]<0)
                    valid=0;
            }

            if(valid==0)
            {
                printf("-1\n");
                continue;
            }

            ll ans=1;

            for(int i=0;i<25;i++)
            {
                if(x.ara[i])
                {
                    ans*=bigmod(prime[i],x.ara[i],m);
                    ans%=m;
                }
            }

            printf("%lld\n",ans);

        }
    }


    return 0;
}

Hackerrank: Lexicographically Smaller or Equal Strings

Posted on by

Problem Link : https://www.hackerrank.com/contests/womens-codesprint-4/challenges/lexicographically-smaller-or-equal-strings

Solution Idea:

    This problem is an example of basic merge sort tree problem. Merge Sort tree is a segment tree in which every node contains a vector. In this problem we can store string in every leaf node of segment tree as the size of the string is <=15. And while merging two leaf node we will merge them in sorted order. Now as the vectors of every node in the segment tree is sorted we can apply binary search on segment tree node to get how many string is lexicographically smaller than the given string.

    So after building merge sort tree we can easily answer every query using binary search.

    If you want to learn some wonderful application of segment tree or merge sort tree you can see this article. 


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#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)             cerr<<#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); cout.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 loop1(i,n)       for(int i=1;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 LINE_PRINT_CASE  printf("Case %d:\n",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;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 100005

vector<string>tree[3*mx],v;

void init(int n, int b, int e)
{
    if(b==e)
    {
        tree[n].pb(v[b]);
        return;
    }
    int l=n*2,r=l+1,mid=(b+e)/2;
    init(l,b,mid);
    init(r,mid+1,e);
    merge(all(tree[l]),all(tree[r]),back_inserter(tree[n]));
//    cout<<n<<" "<<b<<" "<<e<<endl;
//    for(int i=0;i<SZ(tree[n]);i++)
//        cout<<tree[n][i]<<endl;
//    cout<<"-----------------------------"<<endl;
}


int query(int n, int b, int e, int i, int j, string &str)
{
    if(b>j || e<i) return 0;
    if(b>=i && e<=j)
    {
//        int x=upper_bound(all(tree[n]),str)-tree[n].begin();
//        int y=lower_bound(all(tree[n]),str)-tree[n].begin();
//        int z=x-y;
//        return z;
        return upper_bound(all(tree[n]),str)-tree[n].begin();
    }
    int l=n*2,r=l+1,mid=(b+e)/2;
    int p=query(l,b,mid,i,j,str);
    int q=query(r,mid+1,e,i,j,str);
    return p+q;
}


int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int n;
    sf(n);

    v.pb("");
    char sss[30];

    for(int i=0;i<n;i++)
    {
        scanf(" %s",sss);
        v.pb(string(sss));
    }

    init(1,1,n);

    int q;
    sf(q);
    while(q--)
    {
        int a,b;
        sff(a,b);
        scanf(" %s",sss);

        string str=string(sss);
//        cout<<str<<endl;
        int ans=query(1,1,n,a,b,str);
        printf("%d\n",ans);
    }



    return 0;
}

Toph: Another Update-Query Problem

Posted on by

Problem Link : https://toph.co/p/another-update-query-problem

Solution Idea:

    The main idea behind the solution of this problem is simplifying the equation. For a query operation we need the answer of this equation-
    1A_l + (1+d)A_l+1 + (1+2d)A_l+2 + (1+3d)A_l+3 + … + (1+(r-l)d)A_r
    Now let the query range l r is 1 3. and the given array is A=[a1,a2,a3,a4,…]

    So our quation will be-
    1*a1 + (1+d)*a2 + (1+2d)*a3 + (1+3d)*a4
    = a1 + a2 + d*a2 + a3 + 2d*a3 + a4 + 3d*a4
    = (a1+a2+a3+a4) + d*(a2+ 2*a3 + 3*a4)

    Now We can see that first part of this equation is only sum query which can be done using a segment tree and for 2nd part we can use a trick. We can pree calculate the sequence like this-
    1*a1 + 2*a2 + 3*a3 + 4*a4 + 5*a5 + 6*a6 + 7*a7 + ……
    When we need the 2nd part of the equation we can use this equation. We can get the 2nd part of the equation from this equation by this way-
    (2*a2 + 3*a3 + 4*a4)-(a2+a3+a4) = (a2+ 2*a3 + 3*a4).

    Now the above equation is also only a sum equation. We can apply any range sum query or range sum update on this equation and the the first sum equation.

    So if we store this two equation in two segment tree then we can perform range update or query on the segment tree and get any range sum query from the segment tree and using the equation we can answer each query of the problem correctly.


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#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)             cerr<<#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); cout.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 loop1(i,n)       for(int i=1;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 LINE_PRINT_CASE  printf("Case %d:\n",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;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 100005
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2
struct data
{
    ll sum, ssum, prop;
    data()
    {
        sum=0,ssum=0,prop=0;
    }
};

data tree[3*mx];

ll ara[mx];

ll interval_sum(ll b, ll e)
{
    ll x=(e*(e+1))/2;
    ll y=(b*(b-1))/2;
    return (x-y+MOD)%MOD;
}

void push_down(int n, int b, int e)
{
    if(tree[n].prop)
    {
        segment_tree;
        tree[l].sum+=((mid-b+1)*tree[n].prop)%MOD;
        tree[r].sum+=((e-mid)*tree[n].prop)%MOD;
        tree[l].ssum+=(interval_sum(b,mid)*tree[n].prop)%MOD;
        tree[r].ssum+=(interval_sum(mid+1,e)*tree[n].prop)%MOD;
        tree[l].prop+=tree[n].prop%MOD;
        tree[r].prop+=tree[n].prop%MOD;
        tree[l].sum%=MOD;
        tree[l].ssum%=MOD;
        tree[l].prop%=MOD;
        tree[r].sum%=MOD;
        tree[r].ssum%=MOD;
        tree[r].prop%=MOD;
        tree[n].prop=0;
    }
}

void init(int n, int b, int e)
{
    if(b==e)
    {
        tree[n].sum=ara[b]%MOD;
        tree[n].ssum=((ll)b*ara[b])%MOD;
        tree[n].prop=0;
        return;
    }
    segment_tree;
    init(l,b,mid);
    init(r,mid+1,e);
    tree[n].sum=(tree[l].sum+tree[r].sum)%MOD;
    tree[n].ssum=(tree[l].ssum+tree[r].ssum)%MOD;
    tree[n].prop=0;
}

void update(int n, int b, int e, int i, int j, ll val)
{
    if(b>j || e<i) return;
    if(b>=i && e<=j)
    {
        tree[n].sum+=((ll)(e-b+1)*val)%MOD;
        tree[n].ssum+=(interval_sum(b,e)*val)%MOD;
        tree[n].prop+=val;
        tree[n].sum%=MOD;
        tree[n].ssum%=MOD;
        tree[n].prop%=MOD;
        return;
    }
    push_down(n,b,e);
    segment_tree;
    update(l,b,mid,i,j,val);
    update(r,mid+1,e,i,j,val);
    tree[n].ssum=(tree[l].ssum+tree[r].ssum)%MOD;
    tree[n].sum=(tree[l].sum+tree[r].sum)%MOD;
}

data query(int n, int b, int e, int i, int j)
{
    if(b>j || e<i) return data();
    if(b>=i && e<=j)
        return tree[n];
    push_down(n,b,e);
    segment_tree;
    data p=query(l,b,mid,i,j);
    data q=query(r,mid+1,e,i,j);
    data ret;
    ret.ssum=(p.ssum+q.ssum)%MOD;
    ret.sum=(p.sum+q.sum)%MOD;
    return ret;
}

int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int t;
    sf(t);
    TEST_CASE(t)
    {
        int n,q;
        sff(n,q);
        loop1(i,n) sfl(ara[i]);
        init(1,1,n);
        LINE_PRINT_CASE;
        while(q--)
        {
            int a,b,c,d;
            sfff(a,b,c);
            sf(d);
            if(a==1)
            {
                update(1,1,n,b,c,d);
            }
            else
            {
                data ret=query(1,1,n,b,c);
                ll sum=ret.sum;
                ret=query(1,1,n,b+1,c);
                ll ssum=(ret.ssum-(((ll)(b)*ret.sum)%MOD)+MOD)%MOD;
                ssum*=(ll)d%MOD;
                ssum%=MOD;
                ll ans=(sum+ssum)%MOD;
                printf("%lld\n",ans);
            }
        }

    }

    return 0;
}