Problem:


Score : 600 points

Problem Statement

We have a set S of N points in a two-dimensional plane. The coordinates of the i-th point are (x_i, y_i). The N points have distinct x-coordinates and distinct y-coordinates.

For a non-empty subset T of S, let f(T) be the number of points contained in the smallest rectangle, whose sides are parallel to the coordinate axes, that contains all the points in T. More formally, we define f(T) as follows:

f(T) :=  (the number of integers i (1 \leq i \leq N) such that a \leq x_i \leq b and c \leq y_i \leq d, where a, b, c, and d are the minimum x-coordinate, the maximum x-coordinate, the minimum y-coordinate, and the maximum y-coordinate of the points in T)

Find the sum of f(T) over all non-empty subset T of S. Since it can be enormous, print the sum modulo 998244353.

Constraints

1 \leq N \leq 2 \times 10^5

-10^9 \leq x_i, y_i \leq 10^9

x_i \neq x_j (i \neq j)

y_i \neq y_j (i \neq j)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the sum of f(T) over all non-empty subset T of S, modulo 998244353.

Sample Input 1

3
-1 3
2 1
3 -2

Sample Output 1

13

Let the first, second, and third points be P_1, P_2, and P_3, respectively. S = \{P_1, P_2, P_3\} has seven non-empty subsets, and f has the following values for each of them:

f(\{P_1\}) = 1

f(\{P_2\}) = 1

f(\{P_3\}) = 1

f(\{P_1, P_2\}) = 2

f(\{P_2, P_3\}) = 2

f(\{P_3, P_1\}) = 3

f(\{P_1, P_2, P_3\}) = 3

The sum of these is 13.

Sample Input 2

4
1 4
2 1
3 3
4 2

Sample Output 2

34

Sample Input 3

10
19 -11
-3 -12
5 3
3 -15
8 -14
-9 -20
10 -9
0 2
-7 17
6 -6

Sample Output 3

7222

Be sure to print the sum modulo 998244353.



Sample input:
3
-1 3
2 1
3 -2


Sample output:
13

Submission status: Accepted

Solution code:
from itertools import product
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 998244353


class BinaryIndexTree:  # 1-indexed
    def __init__(self, N):
        """
        INPUT
        N [int] -> 全部0で初期化
        N [list] -> そのまま初期化
        """
        if isinstance(N, int):
            self.N = N
            self.depth = N.bit_length()
            self.tree = [0] * (N + 1)
            self.elem = [0] * (N + 1)
        elif isinstance(N, list):
            self.N = len(N)
            self.depth = self.N.bit_length()
            self.tree = [0] + N
            self.elem = [0] + N
            self._init()
        else:
            raise "INVALID INPUT: input must be int or list"

    def _init(self):
        size = self.N
        for i in range(1, self.N):
            if i + (i & -i) > size:
                continue
            self.tree[i + (i & -i)] += self.tree[i]

    def add(self, i, x):
        self.elem[i] += x
        while i <= self.N:
            self.tree[i] += x
            i += i & -i

    def sum(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

    def lower_bound(self, val):
        if val <= 0:
            return 0
        i = 0
        k = 1 << self.depth
        while k:
            if i + k <= self.N and self.tree[i + k] < val:
                val -= self.tree[i + k]
                i += k
            k >>= 1
        return i + 1


def F(a, b, c, d):
    res = 0
    nums = (a, b, c, d)
    ox = tuple(pow(2, i, mod) for i in nums)
    o = tuple(i-1 for i in ox)
    res += ox[0] * o[1] * ox[2] * o[3]
    res %= mod
    res += o[0] * ox[1] * o[2] * ox[3]
    res %= mod
    res -= o[0] * o[1] * o[2] * o[3]
    res %= mod
    res += ox[0] * ox[1] * ox[2] * ox[3]
    res %= mod
    return res


N = int(input())
XY = sorted(tuple(map(int, input().split())) for _ in range(N))
_, Y = zip(*XY)
ytoi = {y: i for i, y in enumerate(sorted(set(Y)), 1)}

bit_R = BinaryIndexTree([1] * N)
bit_L = BinaryIndexTree(N)

ans = 0
for i, y in enumerate(Y, 1):
    R = N - i
    L = i - 1
    y = ytoi[y]
    bit_R.add(y, -1)

    # 点iを原点として、第1-4象限にある点の数
    c4 = bit_R.sum(y)
    c1 = R - c4
    c3 = bit_L.sum(y)
    c2 = L - c3

    ans += F(c1, c2, c3, c4)
    ans %= mod

    bit_L.add(y, 1)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f


def main():
    
    class BIT():#添字は1から始まることに注意
        def __init__(self, max_n):
            self.size = max_n + 1
            self.tree = [0] * self.size
            self.depth = self.size.bit_length()
            self.tot=0
            
        def initialize(self,seq):
            tree = self.tree
            size = self.size
            self.tot=0
            for i,x in enumerate(seq,1):
                self.tot+=x
                tree[i] += x
                j = i+(i&(-i))
                if j < size:
                    tree[j] += tree[i]
            
        def __repr__(self):
            return self.tree.__repr__()
            
        def sum(self,i):
            tree = self.tree
            s = 0
            while i:
                s += tree[i]
                i -= i & -i
            return s
    
        def add(self, i, val):
            tree = self.tree
            size = self.size
            while i < size:
                tree[i] += val
                i += i & -i
            self.tot+=val
        
        def find(self,k):#k番目（最小は１）の要素,使うときは数列のサイズとbitのサイズを合わせること
            if k>self.tot: return self.size
            tree = self.tree; size = self.size
            x,sx = 0,0
            dx = 1 << (self.depth)
            for i in range(self.depth - 1, -1, -1):
                dx = (1 << i)
                if x + dx >= size:
                    continue
                y = x + dx
                sy = sx + tree[y]
                if sy < k:
                    x,sx = y,sy
            return x + 1
    mod = 998244353
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    xs=[]
    ys=[]
    for x,y in S:
        xs.append(x)
        ys.append(y)

    ixsort=argsort(xs)
    iysort=argsort(ys)
    s=[[0,0] for _ in range(N)]

    for i in range(N):
        s[ixsort[i]][0]=i
        s[iysort[i]][1]=i
    
    s.sort()

    xsmall=BIT(N)
    xlarge=BIT(N)
    for i in range(0,N):
        xlarge.add(s[i][1]+1,1)
    
    p2=[0]*(N+1)
    p2[0]=1
    for i in range(1,N+1):
        p2[i]=p2[i-1]*2%mod
    ans=0
    p2n=p2[N]

    for i,(x,y) in enumerate(s):
        xlarge.add(y+1,-1)
        
        lxsy=xlarge.sum(y+1)
        lxly=xlarge.tot-lxsy
        sxsy=xsmall.sum(y+1)
        sxly=xsmall.tot-sxsy

        xsmall.add(y+1,1)
        
        t=1
        t+=p2[lxsy]+p2[lxly]+p2[sxly]+p2[sxsy]-4
        t%=mod
        t+=(p2[lxly+lxsy]-p2[lxly]-p2[lxsy]+1)
        t+=(p2[lxly+sxly]-p2[sxly]-p2[lxly]+1)
        t+=(p2[sxsy+lxsy]-p2[sxsy]-p2[lxsy]+1)
        t+=(p2[sxsy+sxly]-p2[sxsy]-p2[sxly]+1)
        t%=mod
        ans+=p2n-t
        ans%=mod
    print(ans)


        
        



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

class BIT():#添字は1から始まることに注意
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        self.tot=0
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        self.tot=0
        for i,x in enumerate(seq,1):
            self.tot+=x
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, val):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += val
            i += i & -i
        self.tot+=val
    
    def find(self,k):#k番目（最小は１）の要素,使うときは数列のサイズとbitのサイズを合わせること
        if k>self.tot: return self.size
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1

def main():
    mod = 998244353
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    xs=[]
    ys=[]
    for x,y in S:
        xs.append(x)
        ys.append(y)

    ixsort=argsort(xs)
    iysort=argsort(ys)
    s=[[0,0] for _ in range(N)]

    for i in range(N):
        s[ixsort[i]][0]=i
        s[iysort[i]][1]=i
    
    s.sort()

    xsmall=BIT(N)
    xlarge=BIT(N)
    for i in range(0,N):
        xlarge.add(s[i][1]+1,1)
    
    p2=[0]*(N+1)
    p2[0]=1
    for i in range(1,N+1):
        p2[i]=p2[i-1]*2%mod
    ans=0
    p2n=p2[N]
    for i,(x,y) in enumerate(s):
        xlarge.add(y+1,-1)
        
        lxsy=xlarge.sum(y+1)
        lxly=xlarge.tot-lxsy
        sxsy=xsmall.sum(y+1)
        sxly=xsmall.tot-sxsy

        xsmall.add(y+1,1)
        
        t=1
        t+=p2[lxsy]+p2[lxly]+p2[sxly]+p2[sxsy]-4
        t%=mod
        t+=(p2[lxly+lxsy]-p2[lxly]-p2[lxsy]+1)
        t+=(p2[lxly+sxly]-p2[sxly]-p2[lxly]+1)
        t+=(p2[sxsy+lxsy]-p2[sxsy]-p2[lxsy]+1)
        t+=(p2[sxsy+sxly]-p2[sxsy]-p2[sxly]+1)
        t%=mod
        ans+=p2n-t
        ans%=mod
    print(ans)


        
        



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# Enclosed Points
import bisect
from collections import defaultdict


class SegTree():
    # 1-indexed
    def __init__(self, N, function, basement):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)
        X = 2**self.K

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] += value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)


def aggfunc(x, y):
    return x+y


def Press(lists):
    lists.sort()
    d = defaultdict(int)
    now = -float("inf")
    index = 0
    for i in range(len(lists)):
        if lists[i] > now:
            index += 1
            d[lists[i]] = index
            now = lists[i]
        elif lists[i] == now:
            d[lists[i]] = index
    return d


mod = 998244353
N = int(input())
Point = []
for i in range(N):
    x, y = map(int, input().split())
    Point.append((x, y, i))


def modifie():
    Point.sort(key=lambda x: (x[1], x[0]))
    X = []
    for x, y, i in Point:
        X.append(x)
    modified_point_x = Press(X)
    return modified_point_x


modified_point_x = modifie()
segtree = SegTree(N+1, aggfunc, 0)
below_below = defaultdict(int)

for i in range(N):
    x, y, index = Point[i]
    segtree.update(modified_point_x[x], 1)
    below_below[Point[i]] = segtree.query(0, modified_point_x[x]+1)

X, Y = [], []
for x, y, index in Point:
    X.append(x)
    Y.append(y)
X.sort()
Y.sort()

ans = 0
powers = [1 for i in range(3*10**5)]
for i in range(1, 3*10**5):
    powers[i] = powers[i-1]*2 % mod


def pows(K):
    return powers[K]


for i in range(N):
    x, y, index = Point[i]
    ZZ = below_below[Point[i]]-1
    XX = bisect.bisect_right(X, x)-ZZ-1
    WW = bisect.bisect_right(Y, y)-ZZ-1
    YY = N-1-XX-ZZ-WW
    ss = pow(2, N, mod)-1-pows(XX)-pows(YY)-pows(ZZ)-pows(WW)+4-(pows(XX)-1)*(pows(YY)-1) - \
        (pows(YY)-1)*(pows(WW)-1)-(pows(ZZ)-1) * \
        (pows(WW)-1)-(pows(ZZ)-1)*(pows(XX)-1)
    ans += ss
print(ans % mod)

Submission status: Accepted

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, X, Y = I[0], I[1::2], I[2::2]
mod = 998244353


def compress_coord(raw):
    #i_v = {}
    v_i = {}
    for i, v in enumerate(sorted(set(raw))):
        #i_v[i] = v
        v_i[v] = i
    return v_i  #, i_v


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


xi = compress_coord(X)
yj = compress_coord(Y)
X = [xi[x] for x in X]
Y = [yj[y] for y in Y]
LL = [0] * (2 * N)
LR = [0] * (2 * N)
RL = [0] * (2 * N)
RR = [0] * (2 * N)
sortXY = sorted(zip(X, Y))
bit = BinaryIndexedTree(N + 10)
for x, y in sortXY:
    LL[x] = bit.sum(y + 1)
    LR[x] = bit.sum(N + 1) - bit.sum(y + 1)
    bit.add(y + 1, 1)
bit = BinaryIndexedTree(N + 10)
for x, y in sortXY[::-1]:
    RL[x] = bit.sum(y + 1)
    RR[x] = bit.sum(N + 1) - bit.sum(y + 1)
    bit.add(y + 1, 1)
ans = N * (pow(2, N, mod) - 1) % mod
for ll, lr, rl, rr in zip(LL, LR, RL, RR):
    a = pow(2, ll + lr, mod)
    b = pow(2, rl + rr, mod)
    c = pow(2, ll + rl, mod)
    d = pow(2, lr + rr, mod)
    e = pow(2, ll, mod)
    f = pow(2, lr, mod)
    g = pow(2, rl, mod)
    h = pow(2, rr, mod)
    ans -= a + b + c + d
    ans += e + f + g + h
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353

@njit((i8[:], ), cache=True)
def build(raw_data):
    bit = raw_data.copy()
    for i in range(len(bit)):
        j = i + (i & (-i))
        if j < len(bit):
            bit[j] += bit[i]
    return bit


@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i


@njit((i8[:], i8), cache=True)
def find_kth_element(bit, k):
    N = len(bit)
    x, sx = 0, 0
    dx = 1
    while 2 * dx < N:
        dx *= 2
    while dx:
        y = x + dx
        if y < N:
            sy = sx + bit[y]
            if sy < k:
                x, sx = y, sy
        dx //= 2
    return x + 1

@njit((i8[:], ), cache=True)
def main(XY):
    X, Y = XY[::2], XY[1::2]
    N = len(Y)
    ind = X.argsort()
    X, Y = X[ind], Y[ind]
    # 座圧
    Y_sort = Y.copy()
    Y_sort.sort()
    Y = np.searchsorted(Y_sort, Y, 'right')
    bit = np.zeros(N + 10, np.int64)

    pow2 = np.ones(N + 10, np.int64)
    for n in range(1, N + 10):
        pow2[n] = 2 * pow2[n - 1] % MOD

    ret = 0
    for i in range(N):
        y = Y[i]
        L = i
        R = N - 1 - i
        LD = get_sum(bit, y)
        add(bit, y, 1)
        LU = L - LD
        D = y - 1
        U = N - 1 - D
        RD = D - LD
        RU = R - RD

        x = pow2[N] - 1
        x -= pow2[L] + pow2[R] + pow2[D] + pow2[U]
        x += pow2[LD] + pow2[LU] + pow2[RD] + pow2[RU]
        ret += x
    return ret % MOD

N = int(readline())
XY = np.array(read().split(), np.int64)

print(main(XY))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353

N = int(input())
XY = [[int(x) for x in input().split()] for _ in range(N)]
XY.sort() # X ascending
X,Y = zip(*XY)
Y_rank = {x:i for i,x in enumerate(sorted(Y),1)}

def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        x += x & (-x)

def BIT_sum(tree,x):
    ret = 0
    while x:
        ret += tree[x]
        x -= x & (-x)
    return ret

pow2 = [1]
for _ in range(N):
    pow2.append(pow2[-1] * 2 % MOD)

answer = 0
tree = [0] * (N+1)
for L,(x,y) in enumerate(XY):
    y = Y_rank[y]
    R = N - 1 - L
    D = y - 1
    U = N - 1 - D
    LD = BIT_sum(tree,y)
    BIT_update(tree,y)
    LU = L - LD
    RD = D - LD
    RU = R - RD
    # bounding box が自分自身を含むような集合を数える
    # 全体から引く
    cnt = pow2[N]
    cnt -= pow2[L]
    cnt -= pow2[R]
    cnt -= pow2[D]
    cnt -= pow2[U]
    cnt += pow2[LD]
    cnt += pow2[LU]
    cnt += pow2[RD]
    cnt += pow2[RU]
    cnt -= 1
    answer += cnt

answer %= MOD

print(answer)

Submission status: Accepted

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    def compress(list1):
        list2 = sorted(set(list1))
        memo = {value: index for index, value in enumerate(list2)}
        for i in range(len(list1)):
            list1[i] = memo[list1[i]]
        return memo, len(list2)

    # 0許容(i += 1)
    class Bit():
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)
            return

        def sum(self, i):
            i += 1
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x=1):
            i += 1
            # i==0 はだめ => 全部+1するとか
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def search(self, x):
            # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
            # maspyさんの参考　よくわかってない
            i = 0
            s = 0
            step = 1 << ((self.size).bit_length() - 1)
            while step:
                if i + step <= self.size and s + self.tree[i + step] < x:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return i

        def debug(self, k):
            return [self.sum(i) for i in range(k)]

        def inversion(self, A=[3, 10, 1, 8, 5]):
            res = 0
            for i, p in enumerate(A):
                self.add(p, 1)
                res += i + 1 - self.sum(p)
            return res
    N = I()
    S = [LI()for _ in range(N)]
    X = []; Y = []

    for x,y in S:
        X.append(x)
        Y.append(y)

    X_memo, _ = compress(X)
    Y_memo, _ = compress(Y)

    #print(X_memo)
    #print(Y_memo)

    L = [-1]*N

    for i in range(N):
        x, y = S[i]
        L[X_memo[x]] = Y_memo[y]
    #print(L)

    bit = Bit(N)

    ans = pow(2,N-1,mod2)*N %mod2
    #print(ans)
    cnt = 0
    for i, p in enumerate(L):
        #print(bit.debug(N))
        cur1 = N - p - bit.sum(N-1) + bit.sum(p) - 1
        cur2 = bit.sum(p)
        rest = N - cur1 - cur2 - 1
        #print(cur1,cur2,rest)
        cnt += (pow(2,cur2,mod2)-1)*(pow(2,cur1,mod2)-1)*pow(2,rest,mod2)
        cur3 = p - bit.sum(p)
        cur4 = bit.sum(N-1)-bit.sum(p)
        rest = N - cur3 - cur4 - 1
        #print(cur1,cur2,rest)
        cnt += (pow(2,cur3,mod2)-1)*(pow(2,cur4,mod2)-1)*pow(2,rest,mod2)
        cnt -= (pow(2,cur2,mod2)-1)*(pow(2,cur1,mod2)-1)*(pow(2,cur3,mod2)-1)*(pow(2,cur4,mod2)-1)
        #print(cnt)
        bit.add(p, 1)
        cnt %= mod2
    ans += cnt
    ans %= mod2
    print(ans)
    return

def test():
    i = I()
    li = LI()
    lsi = LSI()
    si = LS()
    print(i)
    print(li)
    print(lsi)
    print(si)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
mod = 998244353
a = []
ys = []
for _ in range(N):
  x, y = map(int, input().split())
  a.append((x, y))
  ys.append(y)

def compress(init_val):
  t = sorted(set(init_val))
  d = dict([[t[i], i] for i in range(len(t))])
  res = [0] * len(init_val)
  for i in range(len(init_val)): res[i] = d[init_val[i]]
  return res

ys = compress(ys)
a = [(a[i][0], ys[i] + 1) for i in range(N)]
a.sort()

class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def lowerbound(self, s):
    x = 0
    y = 0
    for i in range(self.n.bit_length(), -1, -1):
      k = x + (1 << i)
      if k <= self.n and (y + self.data[k] < s):
        y += self.data[k]
        x += 1 << i
    return x + 1

fwkl = BIT(N)
fwkr = BIT(N)
ls = [0] * N
rs = [0] * N
for i in range(N):
  ls[i] = fwkl.sum(a[i][1])
  fwkl.add(a[i][1], 1)
for i in range(N - 1, -1, -1):
  rs[i] = fwkr.sum(a[i][1])
  fwkr.add(a[i][1], 1)

table = [pow(2, i, mod) - 1 for i in range(N)]
pw = lambda x: table[x]
#print(ls, rs)
res = 0
for i in range(N):
  ld, rd = ls[i], rs[i]
  lu = i - ld
  ru = N - i - rd - 1
  for k in range(16):
    d = [0] * 4
    t = 1
    if k & 1:
      t *= pw(ld)
      t %= mod
      d[0] = 1
      d[2] = 1
    if k & 2:
      t *= pw(lu)
      t %= mod
      d[0] = 1
      d[3] = 1
    if k & 4:
      t *= pw(rd)
      t %= mod
      d[1] = 1
      d[2] = 1
    if k & 8:
      t *= pw(ru)
      t %= mod
      d[1] = 1
      d[3] = 1
    res += t * (2 ** (sum(d) == 4))
    res %= mod
print(res)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class BitSum:
    def __init__(self, n):
        self.n = n + 1
        self.table = [0] * self.n

    def add(self, i, x):
        i += 1
        while i < self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def main():
    md=998244353
    n=II()
    xy=LLI(n)
    yy=set()
    for x,y in xy:yy.add(y)
    ytoj={y:j for j,y in enumerate(sorted(yy))}

    ans=n*(pow(2,n,md)-1)-4*(pow(2,n,md)-1-n)
    ans%=md

    xy.sort()
    bit=BitSum(200005)
    for i,[x,y] in enumerate(xy):
        j=ytoj[y]
        c=bit.sum(j-1)
        ans+=pow(2,c,md)-1
        ans+=pow(2,i-c,md)-1
        ans%=md
        bit.add(j,1)

    bit=BitSum(200005)
    for i,[x,y] in enumerate(xy[::-1]):
        j=ytoj[y]
        c=bit.sum(j-1)
        ans+=pow(2,c,md)-1
        ans+=pow(2,i-c,md)-1
        ans%=md
        bit.add(j,1)

    print(ans)

main()

Submission status: Accepted

Solution code:
# ref: https://atcoder.jp/contests/abc136/submissions/6696160
# ref: https://atcoder.jp/contests/abc136/submissions/6708692
import sys
input = sys.stdin.readline

n = int(input())
XY = sorted(list(map(int, input().split())) for _ in range(n))
X, Y = zip(*XY)
Y_rank = {z: i for i, z in enumerate(sorted(Y), 1)}

mod = 998244353


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, j):
        while i <= self.n:
            self.data[i] += j
            i += i & -i


po2 = [1]
for i in range(200200):
    po2.append(po2[-1] * 2 % mod)

b = BIT(n)

res = 0
for L, (x, y) in enumerate(XY):
    y = Y_rank[y]
    A = b.sum(y)
    B = L - A
    D = y - 1 - A
    C = n - 1 - A - B - D
    res += po2[n] - (po2[A+B] + po2[B+C] + po2[C+D] + po2[D+A]) + (po2[A] + po2[B] + po2[C] + po2[D]) - 1
    res %= mod
    b.add(y, 1)
print(res)

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    mod = 998244353
    n = int(input())
    xy = [list(map(int, input().split())) for _ in [0]*n]
    ans = 0
    pow_2 = [1]
    j = 1
    for i in range(n):
        j = j*2 % mod
        pow_2.append(j)
    p2 = pow_2[n-1]

    xy.sort(key=lambda x: x[1])
    xy = [(x, i+1) for i, (x, y) in enumerate(xy)]
    xy.sort()

    class BIT():
        def __init__(self, n):
            self.n = n
            self.maxbit = 2**(len(bin(self.n))-3)
            self.bit = [0]*(self.n+1)
            self.allsum = 0

        # 全ての要素に1を足す
        def all_plus(self):
            self.bit = [0]+[i & (-i) for i in range(1, self.n+1)]
            self.allsum = self.n

        # 要素iにvを追加する
        def add(self, i, v):
            x = i
            self.allsum += v
            while x < self.n + 1:
                self.bit[x] += v
                x += x & (-x)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret = 0
            x = i
            while x > 0:
                ret += self.bit[x]
                x -= x & (-x)
            return ret

    bit_left = BIT(n)
    bit_right = BIT(n)
    bit_right.all_plus()

    for i, (x, y) in enumerate(xy):
        bit_right.add(y, -1)
        A = bit_left.sum(y)
        B = i-A
        C = bit_right.sum(y)
        D = n-i-1-C
        bit_left.add(y, 1)
        ans += (pow_2[A]-1)*(pow_2[D]-1)*(pow_2[B+C])
        ans += (pow_2[B]-1)*(pow_2[C]-1)*(pow_2[A+D])
        ans -= (pow_2[B]-1)*(pow_2[C]-1)*(pow_2[A]-1)*(pow_2[D]-1)
        ans += p2
        ans = ans % mod
    print(ans)


main()